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

题目链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1939

来自：刘汝佳大白书P201.

解题思路：

构造一棵线段树，其中每个结点维护三个值，记录最大前缀和，最大后缀和最大连续和。

最大连续和要么完全在左段，要么完全在右段，要么在跨越中线。就是会是左段的最大后缀和+右段的最大前缀和。。。。

代码也是刘汝佳写的哦

代码：

  1 // LA3938 Ray, Pass me the dishes!
  2 // Rujia Liu
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int maxn = 500000 + 10;
  9 const int maxnode = 1000000 + 10;
 10 typedef long long LL;
 11 typedef pair<int,int> Interval;
 12 
 13 LL prefix_sum[maxn];
 14 
 15 LL sum(int L, int R)
 16 {
 17     return prefix_sum[R] - prefix_sum[L-1];
 18 }
 19 
 20 LL sum(Interval p)
 21 {
 22     return sum(p.first, p.second);
 23 }
 24 
 25 Interval better(Interval a, Interval b)
 26 {
 27     if(sum(a) != sum(b)) return sum(a) > sum(b) ? a : b;
 28     return a < b ? a : b; // 利用pair自带的字典序
 29 }
 30 
 31 int qL, qR;
 32 
 33 struct IntervalTree
 34 {
 35     int max_prefix[maxnode];
 36     int max_suffix[maxnode];
 37     Interval max_sub[maxnode];
 38 
 39     void build(int o, int L, int R)
 40     {
 41         if(L == R)
 42         {
 43             max_prefix[o] = max_suffix[o] = L;
 44             max_sub[o] = make_pair(L, L);
 45         }
 46         else
 47         {
 48             int M = L + (R-L)/2;
 49             // 递归创建子树
 50             int lc = o*2, rc = o*2+1;
 51             build(lc, L, M);
 52             build(rc, M+1, R);
 53 
 54             // 递推max_prefix
 55             LL v1 = sum(L, max_prefix[lc]);
 56             LL v2 = sum(L, max_prefix[rc]);
 57             if(v1 == v2) max_prefix[o] = min(max_prefix[lc], max_prefix[rc]);
 58             else max_prefix[o] = v1 > v2 ? max_prefix[lc] : max_prefix[rc];
 59 
 60             // 递推max_suffix
 61             v1 = sum(max_suffix[lc], R);
 62             v2 = sum(max_suffix[rc], R);
 63             if(v1 == v2) max_suffix[o] = min(max_suffix[lc], max_suffix[rc]);
 64             else max_suffix[o] = v1 > v2 ? max_suffix[lc] : max_suffix[rc];
 65 
 66             // 递推max_sub
 67             max_sub[o] = better(max_sub[lc], max_sub[rc]); // 完全在左子树或者右子树
 68             max_sub[o] = better(max_sub[o], make_pair(max_suffix[lc], max_prefix[rc])); // 跨越中线
 69         }
 70     }
 71 
 72     Interval query_prefix(int o, int L, int R)
 73     {
 74         if(max_prefix[o] <= qR) return make_pair(L, max_prefix[o]);
 75         int M = L + (R-L)/2;
 76         int lc = o*2, rc = o*2+1;
 77         if(qR <= M) return query_prefix(lc, L, M);
 78         Interval i = query_prefix(rc, M+1, R);
 79         i.first = L;
 80         return better(i, make_pair(L, max_prefix[lc]));
 81     }
 82 
 83     Interval query_suffix(int o, int L, int R)
 84     {
 85         if(max_suffix[o] >= qL) return make_pair(max_suffix[o], R);
 86         int M = L + (R-L)/2;
 87         int lc = o*2, rc = o*2+1;
 88         if(qL > M) return query_suffix(rc, M+1, R);
 89         Interval i = query_suffix(lc, L, M);
 90         i.second = R;
 91         return better(i, make_pair(max_suffix[rc], R));
 92     }
 93 
 94     Interval query(int o, int L, int R)
 95     {
 96         if(qL <= L && R <= qR) return max_sub[o];
 97         int M = L + (R-L)/2;
 98         int lc = o*2, rc = o*2+1;
 99         if(qR <= M) return query(lc, L, M);
100         if(qL > M) return query(rc, M+1, R);
101         Interval i1 = query_prefix(rc, M+1, R); // 右半的前缀
102         Interval i2 = query_suffix(lc, L, M); // 左半的后缀
103         Interval i3 = better(query(lc, L, M), query(rc, M+1, R));
104         return better(make_pair(i2.first, i1.second), i3);
105     }
106 };
107 
108 IntervalTree tree;
109 
110 int main()
111 {
112     int kase = 0, n, a, Q;
113     while(scanf("%d%d", &n, &Q) == 2)
114     {
115         prefix_sum[0] = 0;
116         for(int i = 0; i < n; i++)
117         {
118             scanf("%d", &a);
119             prefix_sum[i+1] = prefix_sum[i] + a;
120         }
121         tree.build(1, 1, n);
122         printf("Case %d:
", ++kase);
123         while(Q--)
124         {
125             int L, R;
126             scanf("%d%d", &L, &R);
127             qL = L;
128             qR = R;
129             Interval ans = tree.query(1, 1, n);
130             printf("%d %d
", ans.first, ans.second);
131         }
132     }
133     return 0;
134 }

View Code

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

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