fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11.  
  12. int n, q;  
  13. int x[N]; 
  14. ll pref[N]; 
  15.  
  16. ll seg[4 * N], lazy[4 * N]; 
  17.  
  18. void build(int id, int l, int r) {
  19. 	if (l == r) {
  20. 		seg[id] = pref[l]; 
  21. 		return; 
  22. 	}
  23.  
  24. 	int mid = (l + r) >> 1; 
  25. 	build(id * 2, l, mid); 
  26. 	build(id * 2 + 1, mid + 1, r); 
  27.  
  28. 	seg[id] = max(seg[id * 2], seg[id * 2 + 1]); 
  29. }
  30.  
  31. void push(int id) {
  32. 	if (lazy[id]) {
  33. 		seg[id * 2] += lazy[id]; 
  34. 		lazy[id * 2] += lazy[id]; 
  35.  
  36. 		seg[id * 2 + 1] += lazy[id]; 
  37. 		lazy[id * 2 + 1] += lazy[id]; 
  38.  
  39. 		lazy[id] = 0; 	
  40. 	}
  41. }
  42.  
  43. void update(int id, int l, int r, int u, int v, ll val) {
  44. 	if (l > v || r < u) return; 
  45.  
  46. 	if (u <= l && r <= v) {
  47. 		seg[id] += val; 
  48. 		lazy[id] += val; 
  49. 		return; 
  50. 	}
  51.  
  52. 	push(id); 
  53.  
  54. 	int mid = (l + r) >> 1; 
  55. 	update(id * 2, l, mid, u, v, val); 
  56. 	update(id * 2 + 1, mid + 1, r, u, v, val); 
  57.  
  58. 	seg[id] = max(seg[id * 2], seg[id * 2 + 1]); 
  59. }
  60.  
  61. ll getMax(int id, int l, int r, int u, int v) {
  62. 	if (l > v || r < u) return -LINF;   
  63.  
  64. 	if (u <= l && r <= v) return seg[id]; 
  65.  
  66. 	push(id);  
  67.  
  68. 	int mid = (l + r) >> 1; 
  69. 	return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v)); 
  70. }
  71.  
  72. int main() {
  73. 	ios::sync_with_stdio(0); cin.tie(0);  	
  74. 	cin >> n >> q; 
  75. 	for (int i = 1; i <= n; i++) {
  76. 		cin >> x[i]; 
  77. 		pref[i] = pref[i - 1] + x[i]; 
  78. 	}
  79.  
  80. 	build(1, 0, n); 
  81.  
  82. 	while (q--) {
  83. 		int type; cin >> type; 
  84.  
  85. 		if (type == 1) {
  86. 			int pos, val; 
  87. 			cin >> pos >> val;   
  88. 			update(1, 0, n, pos, n, val - x[pos]); 
  89. 			x[pos] = val; 
  90. 		}
  91. 		else {
  92. 			int l, r; 
  93. 			cin >> l >> r; 
  94. 			ll C = getMax(1, 0, n, l - 1, l - 1); // pref[l - 1]
  95. 			ll ans = max(getMax(1, 0, n, l, r) - C, 0ll);
  96. 			cout << ans << '\n';  
  97. 		}
  98. 	}
  99. }
Success #stdin #stdout 0.01s 7684KB
comments (?)
stdin
copy 
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4
stdout
copy 
5
2
0
https://ideone.com/dPIVPd
language:
C++14 (gcc 8.3)
created:
1 year 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!