fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegmentTree{
  5. typedef pair<int, int> pii;
  6. static const int sz = 1 << 17; // sz > MAX_SIZE
  7. static const int inf = 1e9+7;
  8. static pii merge(pii a, pii b){
  9. if(a.first > b.first) return a;
  10. if(a.first < b.first) return b;
  11. if(a.second < b.second) return a;
  12. return b;
  13. }
  14. int n;
  15. pii tree[sz << 1];
  16. int lazy[sz << 1];
  17. bool haveLazy[sz << 1];
  18. void init(int _n){
  19. n = _n;
  20. memset(haveLazy, 0, sizeof haveLazy);
  21. for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
  22. for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
  23. }
  24. void push(int node, int s, int e){
  25. if(!haveLazy[node]) return;
  26. tree[node] = pii(lazy[node], s);
  27. if(s != e){
  28. lazy[node*2] = lazy[node];
  29. lazy[node*2+1] = lazy[node];
  30. haveLazy[node*2] = 1;
  31. haveLazy[node*2+1] = 1;
  32. }
  33. haveLazy[node] = 0;
  34. }
  35. void update(int l, int r, int v, int node, int s, int e){
  36. push(node, s, e);
  37. if(r < s || e < l) return;
  38. if(l <= s && e <= r){
  39. lazy[node] = v;
  40. haveLazy[node] = 1;
  41. push(node, s, e);
  42. return;
  43. }
  44. int m = (s + e) / 2;
  45. update(l, r, v, node*2, s, m);
  46. update(l, r, v, node*2+1, m+1, e);
  47. tree[node] = merge(tree[node*2], tree[node*2+1]);
  48. }
  49. void update(int l, int r, int v){ update(l, r, v, 1, 0, n-1); }
  50. pii query(int l, int r, int node, int s, int e){
  51. push(node, s, e);
  52. if(r < s || e < l) return pii(-inf, inf);
  53. if(l <= s && e <= r) return tree[node];
  54. int m = (s + e) / 2;
  55. pii t1 = query(l, r, node*2, s, m);
  56. pii t2 = query(l, r, node*2+1, m+1, e);
  57. return merge(t1, t2);
  58. }
  59. int query(int l, int r){ return query(l, r, 1, 0, n-1).second; }
  60. };
  61.  
  62. int main(){
  63. ios_base::sync_with_stdio(false); cin.tie(nullptr);
  64. int initialArray[4] = {5, 4, 3, 9};
  65. SegmentTree ST; ST.init(4);
  66. for(int i=0; i<4; i++) ST.update(i, i, initialArray[i]);
  67.  
  68. ST.update(1, 2, 4); // first query (2, 3, 4), [5, 4, 4, 9]
  69. for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  70. cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
  71. ST.update(0, 3, 100); // first query (0, 100), [100, 100, 100, 100]
  72. for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  73. cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 0
  74. ST.update(1, 2, 4); // first query (3, 100), [100, 4, 4, 100]
  75. for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  76. cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
  77. }
Success #stdin #stdout 0s 5932KB
stdin
Standard input is empty
stdout
5 4 4 9 
3
100 100 100 100 
0
100 4 4 100 
0