【SPOJ】1043 Can you answer these queries I

操作：查询区间最大连续和。

每个节点保存当前区间往左，往右的最大和。

往左最大连续和=max（左区间往左最大连续和，左区间的和+右区间往左最大连续和）。

区间最大值=max（左，右区间最大值，左区间右连续+右区间左连续）。

返回答案时，区间需要不断的合并。

 1 #include<cstdio>
 2 #define MAX(a,b) ((a)>(b)?(a):(b))
 3 #define MAXN 50010
 4 #define oo 1000000000
 5 struct node {
 6     int left, right, sum, val;
 7     void Init() {
 8         sum = 0;
 9         left = right = val = -oo;
10     }
11 };
12 node tree[MAXN << 2];
13 inline void PushUp(int rt) {
14     tree[rt].left = MAX(tree[rt << 1].left,
15             tree[rt << 1].sum + tree[rt << 1 | 1].left);
16     tree[rt].right = MAX(tree[rt << 1 | 1].right,
17             tree[rt << 1 | 1].sum + tree[rt << 1].right);
18     tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
19     tree[rt].val = MAX(tree[rt << 1].val, tree[rt << 1 | 1].val);
20     tree[rt].val = MAX(tree[rt].val,
21             tree[rt << 1].right + tree[rt << 1 | 1].left);
22 }
23 void Build(int L, int R, int rt) {
24     if (L == R) {
25         scanf("%d", &tree[rt].val);
26         tree[rt].left = tree[rt].right = tree[rt].sum = tree[rt].val;
27     } else {
28         int mid = (L + R) >> 1;
29         Build(L, mid, rt << 1);
30         Build(mid + 1, R, rt << 1 | 1);
31         PushUp(rt);
32     }
33 }
34 node Query(int x, int y, int L, int R, int rt) {
35     if (x <= L && R <= y)
36         return tree[rt];
37     int mid = (L + R) >> 1;
38     node a, b, res;
39     a.Init(), b.Init(), res.Init();
40     if (x <= mid)
41         a = Query(x, y, L, mid, rt << 1);
42     if (y > mid)
43         b = Query(x, y, mid + 1, R, rt << 1 | 1);
44     res.left = MAX(a.left, a.sum + b.left);
45     res.right = MAX(b.right, b.sum + a.right);
46     res.sum = a.sum + b.sum;
47     res.val = MAX(a.val, b.val);
48     res.val = MAX(res.val, a.right + b.left);
49     return res;
50 }
51 int main() {
52     int n, q, x, y;
53     while (~scanf("%d", &n)) {
54         Build(1, n, 1);
55         scanf("%d", &q);
56         while (q--) {
57             scanf("%d%d", &x, &y);
58             printf("%d\n", Query(x, y, 1, n, 1).val);
59         }
60     }
61     return 0;
62 }