fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define INF 999999999999999999
  5. #define MAXN 300005
  6.  
  7. struct node
  8. {
  9. ll prop;
  10. ll x;
  11. ll sum;
  12. };
  13.  
  14. ll N, Q, ans;
  15. ll arr[MAXN];
  16. node tree[4 * MAXN];
  17.  
  18. void push(ll n, ll l, ll r)
  19. {
  20. ll mid = (l + r) / 2;
  21. ll p = tree[n].x;
  22.  
  23. tree[n].x = 0;
  24. tree[n].prop = 0;
  25.  
  26. tree[2 * n].sum = (mid - l + 1) * p;
  27. tree[2 * n + 1].sum = (r - mid) * p;
  28.  
  29. tree[2 * n].prop = 0;
  30. tree[2 * n].x = p;
  31.  
  32. tree[2 * n + 1].prop = 0;
  33. tree[2 * n + 1].x = p;
  34. }
  35.  
  36. void build(ll n, ll l, ll r)
  37. {
  38. if(l == r)
  39. {
  40. tree[n].prop = 0;
  41. tree[n].x = 0;
  42. tree[n].sum = arr[l];
  43. return ;
  44. }
  45.  
  46. ll mid = (l + r) / 2;
  47. build(2 * n, l, mid);
  48. build(2 * n + 1, mid + 1, r);
  49.  
  50. tree[n].x = 0;
  51. tree[n].prop = 0;
  52. tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum;
  53. }
  54.  
  55. void update_by(ll n, ll l, ll r,ll i, ll j, ll val)
  56. {
  57. if(l > j or r < i)
  58. return ;
  59.  
  60. if(l != r and tree[n].x)
  61. push(n, l, r);
  62.  
  63. if(l >= i and r <= j)
  64. {
  65. tree[n].sum += (val * (r - l + 1));
  66. tree[n].prop += val;
  67. tree[n].x = 0;
  68. return ;
  69. }
  70.  
  71. ll mid = (l + r) / 2;
  72. update_by(2 * n, l, mid, i, j, val);
  73. update_by(2 * n + 1, mid + 1, r, i, j, val);
  74. tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum + ((r - l + 1) * tree[n].prop);
  75. }
  76.  
  77. void update_to(ll n, ll l, ll r, ll i, ll j, ll val)
  78. {
  79. if(l > j or r < i)
  80. return ;
  81.  
  82. if(l != r and tree[n].x)
  83. push(n, l, r);
  84.  
  85. if(l >= i and r <= j)
  86. {
  87. tree[n].prop = 0;
  88. tree[n].x = val;
  89. tree[n].sum = val * (r - l + 1);
  90. return ;
  91. }
  92.  
  93. ll mid = (l + r) / 2;
  94. update_to(2 * n, l, mid, i, j, val);
  95. update_to(2 * n + 1, mid + 1, r, i, j, val);
  96. tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum + ((r - l + 1) * tree[n].prop);
  97. }
  98.  
  99. ll query(ll n, ll l, ll r, ll i, ll j, ll val = 0)
  100. {
  101. if(l > j or r < i)
  102. {
  103. return 0;
  104. }
  105.  
  106. if(l != r and tree[n].x)
  107. push(n, l, r);
  108.  
  109. if(l >= i and r <= j)
  110. {
  111. return tree[n].sum + val * (r - l + 1);
  112. }
  113.  
  114.  
  115. ll mid = (l + r) / 2;
  116. ll p = tree[n].prop;
  117. ll a = query(2 * n, l, mid, i, j, val + p);
  118. ll b = query(2 * n + 1, mid + 1, r, i, j, val + p);
  119. return a + b;
  120. }
  121.  
  122. void solve()
  123. {
  124. cin >> N >> Q;
  125. for(ll i = 1; i <= N; ++ i)
  126. {
  127. cin >> arr[i];
  128. }
  129.  
  130. N = 1 << (ll) ceil(log2(N));
  131. build(1, 1, N);
  132.  
  133. for(ll i = 1; i <= Q; ++ i)
  134. {
  135. ll tt;
  136. cin >> tt;
  137.  
  138. if(tt == 1)
  139. {
  140. ll a, b, x;
  141. cin >> a >> b >> x;
  142. update_by(1, 1, N, a, b, x);
  143. }
  144. else if(tt == 2)
  145. {
  146. ll a, b, x;
  147. cin >> a >> b >> x;
  148. update_to(1, 1, N, a, b, x);
  149. }
  150. else
  151. {
  152. ll a, b;
  153. cin >> a >> b;
  154. cout << query(1, 1, N, a, b) << endl;
  155. }
  156. }
  157. return ;
  158. }
  159.  
  160. int main()
  161. {
  162. std::ios::sync_with_stdio(false);
  163. std::cin.tie(nullptr);
  164.  
  165. // freopen("input.txt","r",stdin);
  166. // freopen("output.txt","w",stdout);
  167.  
  168. solve();
  169. return 0;
  170. }
  171.  
Success #stdin #stdout 0.01s 5532KB
stdin
Standard input is empty
stdout
Standard output is empty