【SPOJ】2916 Can you answer these queries V

操作：
给出x属于[x1,y1]，y属于[x2,y2]，求[x,y]的最大连续和。
将区间分3段考虑，答案可能由某一段的最大连续和，或者某一段往左的最大连续和，某一段往右的最大连续和组合而来。需要特判的是，区间可能存在包含关系。
  1 #include<cstdio>
  2 #define MAX(a,b) ((a)>(b)?(a):(b))
  3 #define MAXN 10010
  4 #define oo 987654321
  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].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
 15     tree[rt].left = MAX(tree[rt<<1].left,tree[rt<<1].sum+tree[rt<<1|1].left);
 16     tree[rt].right =
 17             MAX(tree[rt<<1|1].right,tree[rt<<1|1].sum+tree[rt<<1].right);
 18     tree[rt].val = MAX(tree[rt<<1].val,tree[rt<<1|1].val);
 19     tree[rt].val = MAX(tree[rt].val,tree[rt<<1].right+tree[rt<<1|1].left);
 20 }
 21 void Build(int L, int R, int rt) {
 22     if (L == R) {
 23         scanf("%d", &tree[rt].val);
 24         tree[rt].left = tree[rt].right = tree[rt].sum = tree[rt].val;
 25     } else {
 26         int mid = (L + R) >> 1;
 27         Build(L, mid, rt << 1);
 28         Build(mid + 1, R, rt << 1 | 1);
 29         PushUp(rt);
 30     }
 31 }
 32 node Query(int x, int y, int L, int R, int rt) {
 33     if (x <= L && R <= y)
 34         return tree[rt];
 35     int mid = (L + R) >> 1;
 36     node a, b, res;
 37     a.Init(), b.Init();
 38     if (x <= mid)
 39         a = Query(x, y, L, mid, rt << 1);
 40     if (y > mid)
 41         b = Query(x, y, mid + 1, R, rt << 1 | 1);
 42     res.left = MAX(a.left,a.sum+b.left);
 43     res.right = MAX(b.right,b.sum+a.right);
 44     res.sum = a.sum + b.sum;
 45     res.val = MAX(a.val,b.val);
 46     res.val = MAX(res.val,a.right+b.left);
 47     return res;
 48 }
 49 int main() {
 50     int c, n, q, ans, tmp1, tmp2, x1, y1, x2, y2;
 51     scanf("%d", &c);
 52     while (c--) {
 53         scanf("%d", &n);
 54         Build(1, n, 1);
 55         scanf("%d", &q);
 56         while (q--) {
 57             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
 58             if (y1 <= x2) {
 59                 ans = 0;
 60                 tmp1 = tmp2 = -oo;
 61                 if (y1 + 1 <= x2 - 1)
 62                     ans += Query(y1 + 1, x2 - 1, 1, n, 1).sum;
 63                 if (y1 == x2) {
 64                     tmp1 = Query(x2, y2, 1, n, 1).left;
 65                     ans += tmp1;
 66                     if (x1 <= y1 - 1) {
 67                         tmp2 = Query(x1, y1 - 1, 1, n, 1).right;
 68                         ans += tmp2;
 69                     }
 70                     ans = MAX(ans,tmp1);
 71                     tmp2 = Query(x1, y1, 1, n, 1).right;
 72                     ans = MAX(ans,tmp2);
 73                 } else
 74                     ans += Query(x2, y2, 1, n, 1).left
 75                             + Query(x1, y1, 1, n, 1).right;
 76             } else {
 77                 ans = Query(x2, y1, 1, n, 1).val;
 78                 tmp1 = Query(y1, y2, 1, n, 1).left
 79                         + Query(x1, x2, 1, n, 1).right;
 80                 if (x2 + 1 <= y1 - 1)
 81                     tmp1 += Query(x2 + 1, y1 - 1, 1, n, 1).sum;
 82                 ans = MAX(ans,tmp1);
 83                 tmp1 = Query(x1, x2, 1, n, 1).right;
 84                 if (y1 >= x2)
 85                     ans = MAX(ans,tmp1);
 86                 if (x2 < y2)
 87                     tmp1 += Query(x2 + 1, y2, 1, n, 1).left;
 88                 ans = MAX(ans,tmp1);
 89                 tmp1 = Query(y1, y2, 1, n, 1).left;
 90                 if (x2 <= y1)
 91                     ans = MAX(ans,tmp1);
 92                 if (x1 < y1)
 93                     tmp1 += Query(x1, y1 - 1, 1, n, 1).right;
 94                 ans = MAX(ans,tmp1);
 95             }
 96             printf("%d\n", ans);
 97         }
 98     }
 99     return 0;
100 }