fork(2) download
  1. /*
  2.   author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define pb push_back
  7. #define fr(a,b) for(ll i = a; i < b; i++)
  8. #define mod 1000000007
  9. #define inf (1LL<<60)
  10. #define all(x) (x).begin(), (x).end()
  11. #define prDouble(x) cout << fixed << setprecision(10) << x
  12. #define triplet pair<ll,pair<ll,ll>>
  13. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  14. using namespace std;
  15.  
  16. struct node
  17. {
  18. ll sum;
  19. ll setAll;
  20. ll increment;
  21. bool setAllValid;
  22. node()
  23. {
  24. sum = 0;
  25. setAllValid = 0;
  26. increment = 0;
  27. }
  28. void Reset()
  29. {
  30. setAllValid = increment = 0;
  31. }
  32. };
  33.  
  34. class segtree
  35. {
  36. int range;
  37. vector<node> tree;
  38. public:
  39. void build(vector<int>& v)
  40. {
  41. range = v.size();
  42. tree.assign(4*range, node());
  43. build_recur(v, 0, range-1, 0);
  44. }
  45. void build_recur(vector<int>& v, int l, int r, int node_no)
  46. {
  47. if(l == r){
  48. if(l < v.size())
  49. tree[node_no].sum = v[l];
  50. else tree[node_no].sum = 0;
  51. return;
  52. }
  53. int mid = (l+r)/2;
  54. build_recur(v, l, mid, 2*node_no + 1);
  55. build_recur(v, mid + 1, r, 2*node_no + 2);
  56. tree[node_no].sum = tree[2*node_no + 1].sum + tree[2*node_no + 2].sum;
  57. }
  58. ll range_query(int L, int R)
  59. {
  60. return range_query_recur(0, 0, range - 1, L, R);
  61. }
  62.  
  63. void incUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
  64. {
  65. if(r < L || R < l || l >= range)
  66. return;
  67. if(L <= l && R >= r)
  68. {
  69. tree[node].increment += X;
  70. return;
  71. }
  72. applyAggr(node,l,r);
  73. int mid = (l+r)/2;
  74. incUpdate_recur(2*node+1,l,mid,L,R,X);
  75. incUpdate_recur(2*node+2,mid+1,r,L,R,X);
  76. applyAggr(2*node+1, l, mid);
  77. applyAggr(2*node+2, mid+1, r);
  78. tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
  79. }
  80.  
  81. void incUpdate(int L, int R, int X)
  82. {
  83. incUpdate_recur(0,0,range-1,L,R,X);
  84. }
  85.  
  86. void setUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
  87. {
  88. if(r < L || R < l || l >= range)
  89. return;
  90. if(L <= l && R >= r)
  91. {
  92. tree[node].setAllValid = 1;
  93. tree[node].setAll = X;
  94. tree[node].increment = 0;
  95. return;
  96. }
  97. applyAggr(node,l,r);
  98. int mid = (l+r)/2;
  99. setUpdate_recur(2*node+1,l,mid,L,R,X);
  100. setUpdate_recur(2*node+2,mid+1,r,L,R,X);
  101. applyAggr(2*node+1, l, mid);
  102. applyAggr(2*node+2, mid+1, r);
  103. tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
  104. }
  105.  
  106. void setUpdate(int L, int R, int X)
  107. {
  108. setUpdate_recur(0,0,range-1,L,R,X);
  109. }
  110.  
  111. void compose(int par, int child)
  112. {
  113. if(tree[par].setAllValid){
  114. tree[child].setAllValid = 1;
  115. tree[child].setAll = tree[par].setAll;
  116. tree[child].increment = tree[par].increment;
  117. }
  118. else tree[child].increment += tree[par].increment;
  119. }
  120.  
  121. void applyAggr(int node, int l, int r)
  122. {
  123. if(tree[node].setAllValid)
  124. tree[node].sum = (r-l+1)*tree[node].setAll;
  125.  
  126. tree[node].sum += (r-l+1)*tree[node].increment;
  127.  
  128. if(l != r){
  129. compose(node, 2*node + 1);
  130. compose(node, 2*node + 2);
  131. }
  132.  
  133. tree[node].Reset();
  134. }
  135.  
  136. ll range_query_recur(int node, int l, int r, int& L, int& R)
  137. {
  138. if(r < L || R < l || l >= range)
  139. return 0;
  140. applyAggr(node, l, r);
  141. if(L <= l && R >= r)
  142. return tree[node].sum;
  143. int mid = (l+r)/2;
  144. return range_query_recur(2*node + 1, l, mid, L, R) + range_query_recur(2*node + 2, mid+1, r, L, R);
  145. }
  146. };
  147.  
  148. int main() {
  149. fast_io;
  150. int n,q;
  151. cin >> n >> q;
  152.  
  153. vector<int> v(n);
  154. for(int i = 0; i < n; i++)
  155. cin >> v[i];
  156.  
  157. segtree sg;
  158. sg.build(v);
  159.  
  160. while(q--)
  161. {
  162. int t;
  163. cin >> t;
  164. if(t == 1){
  165. int a,b,x;
  166. cin >> a >> b >> x;
  167. sg.incUpdate(a-1,b-1,x);
  168. }
  169. else if(t == 2){
  170. int a,b,x;
  171. cin >> a >> b >> x;
  172. sg.setUpdate(a-1,b-1,x);
  173. }
  174. else {
  175. int a,b;
  176. cin >> a >> b;
  177. cout << sg.range_query(a-1,b-1) <<'\n';
  178. }
  179. }
  180. return 0;
  181. }
  182.  
Success #stdin #stdout 0s 4564KB
stdin
6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5
stdout
7
11
15