fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. const int maxn = 50050;
  9. int n, m, x, y, op, val[maxn];
  10.  
  11. struct SegNode {
  12. 	int left, right, sum, maxLeft, maxRight, maxAll;
  13. 	int mid() { return (left + right) >> 1; }
  14. };
  15.  
  16. struct SegmentTree {
  17.  
  18. 	SegNode tree[maxn*5];
  19.  
  20. 	SegNode pushUp(SegNode left, SegNode right) {
  21. 		SegNode update;
  22. 		update.sum = left.sum + right.sum;
  23. 		update.maxLeft = max(left.maxLeft, left.sum + right.maxLeft);
  24. 		update.maxRight = max(right.maxRight, right.sum + left.maxRight);
  25. 		update.maxAll = max(max(left.maxAll, right.maxAll), left.maxRight + right.maxLeft);
  26. 		return update;
  27. 	}
  28.  
  29. 	void build(int left, int right, int idx) {
  30. 		tree[idx].left = left; tree[idx].right = right;
  31. 		if (left == right) {
  32. 			tree[idx].sum = tree[idx].maxLeft = tree[idx].maxRight = tree[idx].maxAll = val[left];
  33. 			return ;
  34. 		}
  35. 		int mid = tree[idx].mid();
  36. 		build(left, mid, idx<<1); build(mid+1, right, idx<<1|1);
  37. 		SegNode update = pushUp(tree[idx<<1], tree[idx<<1|1]);
  38. 		tree[idx].sum = update.sum; tree[idx].maxLeft = update.maxLeft;
  39. 		tree[idx].maxRight = update.maxRight; tree[idx].maxAll = update.maxAll;
  40. 	}
  41.  
  42. 	void update(int pos, int value, int idx) {
  43. 		if (tree[idx].left == tree[idx].right) {
  44. 			tree[idx].maxAll = value; tree[idx].sum = value; tree[idx].maxLeft = value;
  45. 			tree[idx].maxRight = value; return ;
  46. 		}
  47. 		int mid = tree[idx].mid();
  48. 		if (pos <= mid) update(pos, value, idx<<1);
  49. 		else update(pos, value, idx<<1|1);
  50. 		SegNode update = pushUp(tree[idx<<1], tree[idx<<1|1]);
  51. 		tree[idx].sum = update.sum; tree[idx].maxLeft = update.maxLeft;
  52. 		tree[idx].maxRight = update.maxRight; tree[idx].maxAll = update.maxAll;
  53. 	}
  54.  
  55. 	SegNode query(int left, int right, int idx) {
  56. 		if (tree[idx].left >= left && tree[idx].right <= right)
  57. 			return tree[idx];
  58. 		int mid = tree[idx].mid();
  59. 		if (right <= mid) return query(left, right, idx<<1);
  60. 		else if (left > mid) return query(left, right, idx<<1|1);
  61. 		else return pushUp(query(left, mid, idx<<1), query(mid+1, right, idx<<1|1));  
  62. 	}
  63. };
  64.  
  65. SegmentTree seg;
  66.  
  67. int main() {
  68. 	scanf("%d", &n);
  69. 	for (int i = 1; i <= n; i++)
  70. 		scanf("%d", val + i);
  71. 	seg.build(1, n, 1); scanf("%d", &m);
  72. 	for (int i = 1; i <= m; i++) {
  73. 		scanf("%d %d %d", &op, &x, &y);
  74. 		if (op == 1) printf("%d\n", seg.query(x, y, 1).maxAll);
  75. 		else seg.update(x, y, 1);
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 8968KB
comments (?)
stdin
copy 
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
stdout
copy 
6
4
-3
https://ideone.com/MsopAu
SPOJ GSS3
language:
C++ (gcc 8.3)
created:
11 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!