fork download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6. #define endl '\n'
  7. #define ll long long
  8. #define pi pair<int, int>
  9. #define f first
  10. #define s second
  11.  
  12. const int mxn = 200000;
  13. int n, q;
  14. ll a[mxn];
  15.  
  16. struct segTree{
  17. int l, r;
  18. segTree *tl, *tr;
  19. ll vl, lz, mn1, mn2, mnz, mx1, mx2, mxz;
  20.  
  21. segTree(int l, int r) : l(l), r(r){
  22. vl = lz = mn1 = mn2 = mx1 = mx2 = 0, mnz = mxz = r - l + 1;
  23. if(l != r){
  24. int mid = (l + r) / 2;
  25. tl = new segTree(l, mid);
  26. tr = new segTree(mid + 1, r);
  27. pul();
  28. }else{
  29. upd(a[l]);
  30. }
  31. }
  32.  
  33. void upd(ll x){
  34. vl += (r - l + 1) * x;
  35. lz += x;
  36. mn1 += x, mn2 += x;
  37. mx1 += x, mx2 += x;
  38. }
  39.  
  40. void updmn(ll x){
  41. if(x >= mx1) return;
  42. vl += mxz * (x - mx1), mx1 = x, mn2 = min(mn2, x);
  43. if(x <= mx2) mn1 = mx2 = x;
  44. }
  45.  
  46. void updmx(ll x){
  47. if(x <= mn1) return;
  48. vl += mnz * (x - mn1), mn1 = x, mx2 = max(mx2, x);
  49. if(x >= mn2) mn2 = mx1 = x;
  50. }
  51.  
  52. void psh(){
  53. tl->upd(lz), tr->upd(lz), lz = 0;
  54. tl->updmn(mx1), tr->updmn(mx1);
  55. tl->updmx(mn1), tr->updmx(mn1);
  56. }
  57.  
  58. void pul(){
  59. vl = tl->vl + tr->vl;
  60.  
  61. {
  62. vector<ll> v = {tl->mn1, tl->mn2, tr->mn1, tr->mn2};
  63. sort(v.begin(), v.end());
  64. v.erase(unique(v.begin(), v.end()), v.end());
  65. mn1 = mn2 = v[0];
  66. if(v.size() > 1) mn2 = v[1];
  67. mnz = (tl->mn1 == mn1) * tl->mnz + (tr->mn1 == mn1) * tr->mnz;
  68. }
  69.  
  70. {
  71. vector<ll> v = {tl->mx1, tl->mx2, tr->mx1, tr->mx2};
  72. sort(v.begin(), v.end(), greater<ll>());
  73. v.erase(unique(v.begin(), v.end()), v.end());
  74. mx1 = mx2 = v[0];
  75. if(v.size() > 1) mx2 = v[1];
  76. mxz = (tl->mx1 == mx1) * tl->mxz + (tr->mx1 == mx1) * tr->mxz;
  77. }
  78. }
  79.  
  80. void add(int x, int y, ll z){
  81. if(y < l || r < x) return;
  82. if(x <= l && r <= y) return upd(z);
  83. psh();
  84. tl->add(x, y, z), tr->add(x, y, z);
  85. pul();
  86. }
  87.  
  88. void addmn(int x, int y, ll z){
  89. if(y < l || r < x) return;
  90. if(x <= l && r <= y && (z > mx2 || mx1 == mx2)) return updmn(z);
  91. psh();
  92. tl->addmn(x, y, z), tr->addmn(x, y, z);
  93. pul();
  94. }
  95.  
  96. void addmx(int x, int y, ll z){
  97. if(y < l || r < x) return;
  98. if(x <= l && r <= y && (z < mn2 || mn1 == mn2)) return updmx(z);
  99. psh();
  100. tl->addmx(x, y, z), tr->addmx(x, y, z);
  101. pul();
  102. }
  103.  
  104. ll qry(int x, int y){
  105. if(y < l || r < x) return 0;
  106. if(x <= l && r <= y) return vl;
  107. psh();
  108. return tl->qry(x, y) + tr->qry(x, y);
  109. }
  110. };
  111.  
  112. int main(){
  113. ios::sync_with_stdio(0);
  114. cin.tie(0);
  115.  
  116. cin >> n >> q;
  117.  
  118. for(int i = 0; i < n; i++) cin >> a[i];
  119.  
  120. segTree tre(0, n - 1);
  121. while(q--){
  122. ll t, x, y, z;
  123. cin >> t >> x >> y; if(t < 3) cin >> z;
  124. y--;
  125. switch(t){
  126. case 0:
  127. tre.addmn(x, y, z);
  128. break;
  129. case 1:
  130. tre.addmx(x, y, z);
  131. break;
  132. case 2:
  133. tre.add(x, y, z);
  134. break;
  135. case 3:
  136. cout << tre.qry(x, y) << endl;
  137. break;
  138. }
  139. }
  140.  
  141. return 0;
  142. }
Success #stdin #stdout 0.01s 5544KB
stdin
1 2
67
3 0 1 25
1 0 1 32
stdout
67