fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define endl '\n'
  6. #define inf 1e15
  7. #define vi vector<int>
  8. #define pi pair<int, int>
  9. #define F0(n, i) for(int i = 0; i < n; i++)
  10. #define each(a) for(auto& e: a)
  11. #define F first
  12. #define S second
  13.  
  14. struct node {
  15. 	pi mx_pfx, mn_pfx, mx_sfx, mn_sfx, mxs, tot;
  16. 	node(int x) {
  17. 		mx_pfx = mn_pfx = mx_sfx = mn_sfx = mxs = tot = {x, 1};
  18. 	}
  19. 	node() {
  20. 		mx_pfx = mx_sfx = mxs = {-inf, 0};
  21. 		mn_pfx = mn_sfx = {inf, 0};
  22. 		tot = {0, 0}; // useless
  23. 	}
  24. 	void dbg() {
  25. 		cerr << mx_pfx.F << ' ' << mn_pfx.F << ' ' << mx_sfx.F << ' ' << mn_sfx.F << ' ' << mxs.F << ' ' << tot.F << endl;
  26. 	}
  27. };
  28.  
  29. template<typename T>
  30. class segtree {
  31. public:
  32. 	vector<T> t;
  33. 	int n;
  34. 	T def;
  35. 	function<T(T, T)> fx;
  36. 	void build(int _n, T _def, function<T(T, T)> _fx) {
  37. 		n = _n; def = _def; fx = _fx;
  38. 		t.assign(n * 2, def);
  39. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  40. 	}
  41. 	void build(vector<int>& a, T _def, function<T(T, T)> _fx) {
  42. 		n = a.size(); def = _def; fx = _fx;
  43. 		t.assign(n * 2, def);
  44. 		F0(n, i) t[i + n] = T(a[i]);
  45. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  46. 	}
  47. 	void update(int i, int v) {
  48. 		for(t[i += n] = T(v); i > 1; ) {
  49. 			i /= 2;
  50. 			t[i] = fx(t[i * 2], t[i * 2 + 1]);
  51. 		}
  52. 	}
  53. 	// this query is made on [l, r)
  54. 	T query(int l, int r) {
  55. 		cerr << l << ' ' << r << endl;
  56. 		T lans = def, rans = def;
  57. 		for(l += n, r += n; l < r; l /= 2, r /= 2) {
  58. 			if(l % 2) lans = fx(lans, t[l++]);
  59. 			if(r % 2) rans = fx(t[--r], rans);
  60. 		}
  61. 		lans.dbg(); rans.dbg();
  62. 		return fx(lans, rans);
  63. 	}
  64. 	void debug() {
  65. 		each(t) e.dbg();
  66. 	}
  67. };
  68.  
  69. void solve() {
  70. 	int n;
  71. 	cin >> n;
  72. 	vi a(n);
  73. 	F0(n, i) cin >> a[i];
  74. 	segtree<node> MaxSum;
  75. 	auto fx = [&](node x, node y) {
  76. 		node ans;
  77. 		//////////
  78. 		int mx_pfx = max(x.mx_pfx.F, x.tot.F + (x.tot.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F));
  79. 		ans.mx_pfx.F = mx_pfx;
  80. 		if(mx_pfx == x.mx_pfx.F) 
  81. 			ans.mx_pfx.S = x.mx_pfx.S;
  82. 		if(mx_pfx == x.tot.F + (x.tot.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F)) 
  83. 			ans.mx_pfx.S = x.tot.S + (x.tot.S % 2 ? y.mn_pfx.S : y.mx_pfx.S);
  84. 		//////////
  85. 		int mn_pfx = min(x.mn_pfx.F, x.tot.F + (x.tot.S % 2 ? -y.mx_pfx.F : y.mn_pfx.F));
  86. 		ans.mn_pfx.F = mn_pfx;
  87. 		if(mn_pfx == x.mn_pfx.F) 
  88. 			ans.mn_pfx.S = x.mn_pfx.S;
  89. 		if(mn_pfx == x.tot.F + (x.tot.S % 2 ? -y.mx_pfx.F : y.mn_pfx.F)) 
  90. 			ans.mn_pfx.S = x.tot.S + (x.tot.S % 2 ? y.mx_pfx.S : y.mn_pfx.S);
  91. 		//////////
  92. 		int mx_sfx = max(y.mx_sfx.F, x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.tot.F : y.tot.F));
  93. 		ans.mx_sfx.F = mx_sfx;
  94. 		if(mx_sfx == y.mx_sfx.F) 
  95. 			ans.mx_sfx.S = y.mx_sfx.S;
  96. 		if(mx_sfx == x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.tot.F : y.tot.F)) 
  97. 			ans.mx_sfx.S = x.mx_sfx.S + y.tot.S;
  98. 		//////////
  99. 		int mn_sfx = min(y.mn_sfx.F, x.mn_sfx.F + (x.mn_sfx.S % 2 ? -y.tot.F : y.tot.F));
  100. 		ans.mn_sfx.F = mn_sfx;
  101. 		if(mn_sfx == y.mn_sfx.F) 
  102. 			ans.mn_sfx.S = y.mn_sfx.S;
  103. 		if(mn_sfx == x.mn_sfx.F + (x.mn_sfx.S % 2 ? -y.tot.F : y.tot.F)) 
  104. 			ans.mn_sfx.S = x.mn_sfx.S + y.tot.S;
  105. 		//////////
  106. 		int mxs = max({ x.mxs.F, y.mxs.F, x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F) });
  107. 		ans.mxs.F = mxs;
  108. 		if(mxs == x.mxs.F)
  109. 			ans.mxs.S = x.mxs.S;
  110. 		if(mxs == y.mxs.F)
  111. 			ans.mxs.S = y.mxs.S;
  112. 		if(mxs == x.mx_sfx.F + (x.mx_sfx.S % 2 ? -y.mn_pfx.F : y.mx_pfx.F))
  113. 			ans.mxs.S = x.mx_sfx.S + (x.mx_sfx.S % 2 ? y.mn_pfx.S : y.mx_pfx.S);
  114. 		//////////
  115. 		ans.tot = {x.tot.F + (x.tot.S % 2 ? -y.tot.F : y.tot.F), x.tot.S + y.tot.S};
  116. 		return ans;
  117. 	};
  118. 	MaxSum.build(a, node(), fx);
  119. 	int q, mod = 1e9 + 7;
  120. 	cin >> q;
  121. 	while(q--) {
  122. 		int t;
  123. 		cin >> t;
  124. 		MaxSum.debug();
  125. 		cerr << endl;
  126. 		if(t == 1) {
  127. 			int i, v;
  128. 			cin >> i >> v;
  129. 			i--;
  130. 			MaxSum.update(i, v);
  131. 		} else {
  132. 			int l, r;
  133. 			cin >> l >> r;
  134. 			l--;
  135. 			node ans = MaxSum.query(l, r);
  136. 			cout << ans.mxs.F % mod << ' ';
  137. 		}
  138. 	}
  139. }
  140.  
  141. int32_t main() {
  142. 	int t = 1;
  143. 	cin >> t;
  144. 	while(t--) {
  145. 		solve();
  146. 		cout << endl;
  147. 	}
  148. }
Success #stdin #stdout #stderr 0.01s 5436KB
comments (?)
stdin
copy 
2
5
1 -2 3 4 5
3
2 1 5
1 4 -1
2 1 5
5
2 4 -10 3 7
4
2 1 2
2 3 4
2 1 5
2 2 3
stdout
copy 
7 12 
4 3 17 14
stderr
copy 
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
5 -1 3 -5 5 5
4 -1 4 0 5 0
-2 -5 3 -5 3 -5
4 -1 5 -1 5 -1
1 1 1 1 1 1
-2 -2 -2 -2 -2 -2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

0 5
6 1 6 -5 6 6
4 -1 5 -1 5 -1
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
5 -1 3 -5 5 5
4 -1 4 0 5 0
-2 -5 3 -5 3 -5
4 -1 5 -1 5 -1
1 1 1 1 1 1
-2 -2 -2 -2 -2 -2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
0 -6 3 -5 5 0
-1 -6 4 -5 5 -5
-2 -5 3 -5 3 -5
-1 -6 5 -6 5 -6
1 1 1 1 1 1
-2 -2 -2 -2 -2 -2
3 3 3 3 3 3
-1 -1 -1 -1 -1 -1
5 5 5 5 5 5

0 5
6 1 6 -5 6 6
-1 -6 5 -6 5 -6
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
3 -16 19 -16 19 -16
3 -4 5 -2 7 -2
14 4 14 -10 14 14
3 -4 7 -4 7 -4
2 2 2 2 2 2
4 4 4 4 4 4
-10 -10 -10 -10 -10 -10
3 3 3 3 3 3
7 7 7 7 7 7

0 2
2 2 2 2 2 2
4 4 4 4 4 4
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
3 -16 19 -16 19 -16
3 -4 5 -2 7 -2
14 4 14 -10 14 14
3 -4 7 -4 7 -4
2 2 2 2 2 2
4 4 4 4 4 4
-10 -10 -10 -10 -10 -10
3 3 3 3 3 3
7 7 7 7 7 7

2 4
-10 -10 -10 -10 -10 -10
3 3 3 3 3 3
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
3 -16 19 -16 19 -16
3 -4 5 -2 7 -2
14 4 14 -10 14 14
3 -4 7 -4 7 -4
2 2 2 2 2 2
4 4 4 4 4 4
-10 -10 -10 -10 -10 -10
3 3 3 3 3 3
7 7 7 7 7 7

0 5
2 -12 14 -12 14 -12
3 -4 7 -4 7 -4
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
3 -16 19 -16 19 -16
3 -4 5 -2 7 -2
14 4 14 -10 14 14
3 -4 7 -4 7 -4
2 2 2 2 2 2
4 4 4 4 4 4
-10 -10 -10 -10 -10 -10
3 3 3 3 3 3
7 7 7 7 7 7

1 3
14 4 14 -10 14 14
-1000000000000000 1000000000000000 -1000000000000000 1000000000000000 -1000000000000000 0
https://ideone.com/LFGNGG
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

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!