LA 3938 动态最大连续和（线段树）

题意：
给出一个长度为n的整数序列D，你的任务是对m个询问作出回答。对于询问（a，b），需要找到两个下标x和y，使得a≤x≤y≤b，并且Dx+Dx+1+...+Dy尽量大。如果有多组满足条件的x和y，x应该尽量小。如果还有多解，y应该尽量小。
思路：
线段树。
这道题目挺麻烦的，也是参考了刘汝佳的代码。
  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int maxn = 1000000 + 5;
  7 typedef pair<int, int> Interval;
  8 
  9 int n, m;
 10 long long sum[maxn];
 11 int QL, QR;
 12 
 13 struct node
 14 {
 15     Interval max_sub;  //最大连续和
 16     int max_prefix;    //最大前缀和
 17     int max_suffix;    //最大后缀和
 18 }t[maxn];
 19 
 20 
 21 long long cacl(int L, int R)
 22 {
 23     return sum[R] - sum[L - 1];
 24 }
 25 
 26 Interval better(Interval a, Interval b)
 27 {
 28     if (cacl(a.first, a.second) != cacl(b.first, b.second))
 29         return cacl(a.first, a.second) > cacl(b.first, b.second) ? a : b;
 30     return a < b ? a : b;
 31 }
 32 
 33 void build_tree(int L, int R, int k)
 34 {
 35     if (L == R)
 36     {
 37         t[k].max_prefix = L;
 38         t[k].max_suffix = L;
 39         t[k].max_sub = make_pair(L, L);
 40         return;
 41     }
 42     else
 43     {
 44         int mid = (L + R) / 2;
 45         int lc = 2 * k, rc = 2 * k + 1;
 46         build_tree(L, mid, lc);
 47         build_tree(mid + 1, R, rc);
 48 
 49         //计算最大前缀和
 50         long long x1 = cacl(L, t[lc].max_prefix);
 51         long long x2 = cacl(L, t[rc].max_prefix);
 52         if (x1 == x2)  t[k].max_prefix = min(t[lc].max_prefix, t[rc].max_prefix);
 53         else t[k].max_prefix = x1 > x2 ? t[lc].max_prefix : t[rc].max_prefix;
 54 
 55         //计算最大后缀和
 56         x1 = cacl(t[lc].max_suffix, R);
 57         x2 = cacl(t[rc].max_suffix, R);
 58         if (x1 == x2)  t[k].max_suffix = min(t[lc].max_suffix, t[rc].max_suffix);
 59         else t[k].max_suffix = x1 > x2 ? t[lc].max_suffix : t[rc].max_suffix;
 60 
 61         //计算最大连续和
 62         t[k].max_sub = better(t[lc].max_sub, t[rc].max_sub);
 63         t[k].max_sub = better(t[k].max_sub, make_pair(t[lc].max_suffix, t[rc].max_prefix));
 64     }
 65 }
 66 
 67 
 68 Interval query_suffix(int L, int R, int k)
 69 {
 70     if (t[k].max_suffix >= QL)  return make_pair(t[k].max_suffix, R);
 71     int mid = (L + R) / 2;
 72     int lc = 2 * k, rc = 2 * k + 1;
 73     if (QL > mid)  return query_suffix(mid + 1, R, rc);
 74     Interval x = query_suffix(L, mid, lc);
 75     x.second = R;
 76     return better(x, make_pair(t[rc].max_suffix, R));
 77 }
 78 
 79 
 80 Interval query_prefix(int L, int R, int k)
 81 {
 82     if (QR >= t[k].max_prefix)  return make_pair(L, t[k].max_prefix);
 83     int mid = (L + R) / 2;
 84     int lc = 2 * k, rc = 2 * k + 1;
 85     if (QR <= mid)   return query_prefix(L, mid, lc);
 86     Interval x = query_prefix(mid + 1, R, rc);
 87     x.first = L;
 88     return better(x, make_pair(L, t[lc].max_prefix));
 89 }
 90 
 91 Interval query(int L, int R, int k)
 92 {
 93     if (QL <= L && QR >= R)   return t[k].max_sub;
 94     int mid = (L + R) / 2;
 95     int lc = 2 * k;
 96     int rc = 2 * k + 1;
 97     if (QR <= mid)  return query(L, mid, lc);     //完全在左半段
 98     if (QL > mid)   return query(mid + 1, R, rc); //完全在右半段
 99     Interval x1 = query_suffix(L, mid, lc);      //左半段的后缀
100     Interval x2 = query_prefix(mid + 1, R, rc);  //右半段的前缀
101     Interval x3 = better(query(L, mid, lc), query(mid + 1, R, rc));
102     return better(make_pair(x1.first, x2.second), x3);
103 }
104 
105 int main()
106 {
107     //freopen("D:\txt.txt", "r", stdin);
108     int x;
109     int kase = 0;
110     while (~scanf("%d%d", &n, &m))
111     {
112         sum[0] = 0;
113         for (int i = 1; i <= n; i++)
114         {
115             scanf("%d", &x);
116             sum[i] = sum[i - 1] + x;
117         }
118         build_tree(1, n, 1);
119         printf("Case %d:
", ++kase);
120         while (m--)
121         {
122             scanf("%d%d", &QL, &QR);
123             Interval ans = query(1, n, 1);
124             printf("%d %d
", ans.first, ans.second);
125         }
126     }
127 }