fork download
copy 
  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
comments (?)
stdin
copy 
1 2
67
3 0 1 25
1 0 1 32
stdout
copy 
67
https://ideone.com/uxzmp2
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!