POJ 2750 Potted Flower 线段树区间合并

题目大意：一个圆环上有n(4<= n <= 100000)个数字，编号依次从1到n，第n个数与第1个数相连。规则是：从环上选取任意个数（但不能为0也不能取全部）的连续数字，使选取数字之和最大。但现在有m(4<= m <= 100000)个操作，用a, b两个数字来描述，意思是：将环上编号为a的数字换成b。现要求每次操作后都按照规则输出最大之和。更多细节点击传送门。

思路：因为查询次数太大，用线段树来维护数据。将圆环从编号为1和n的数字间断开，扯成直线。因不能选择全部数字的限制，将情况分成两种。

1. 圆环上的数全是正数。所有数字之和减去其中最小的一个数，即为结果。

2. 圆环上的数有负数。此时有两种选取数字的方式：

　　1. 所选的连续数字包含编号1和n的两个数。此时在线段树内他们并不连续（在1和n之间被断开了）。所有数字之和减去线段树区间内数字最小之和即为结果。

　　2. 所选的连续数字不包含1和n两个数。用线段树维护出区间内最大连续数字之和即可。

线段树需要维护7个数据：sum, lmax, rmax, tmax, lmin, rmin, tmin。

其中lmax意为从区间左端第一个数开始的最大连续数字之和，rmax意为从区间右端第一个数开始的最大连续数字之和，tmax意为整个区间的最大连续数字之和。 min同理。

至于条件判定，当圆环上全是正数时，对于整个区间有sum=tmax。

各区间合并的具体公式见代码中PushUp函数。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define maxn 100010
 4 #define lson l, m, rt << 1
 5 #define rson m + 1, r, rt << 1 | 1
 6 using namespace std;
 7 int sum[maxn<<2], lmax[maxn<<2], rmax[maxn<<2], tmax[maxn<<2];
 8 int lmin[maxn<<2], rmin[maxn<<2], tmin[maxn<<2];
 9 void PushUp(int rt)
10 {
11     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
12     lmax[rt] = max(lmax[rt<<1], sum[rt<<1] + lmax[rt<<1|1]);
13     rmax[rt] = max(rmax[rt<<1|1], sum[rt<<1|1] + rmax[rt<<1]);
14     tmax[rt] = max(tmax[rt<<1], max(tmax[rt<<1|1], rmax[rt<<1] + lmax[rt<<1|1]));
15     lmin[rt] = min(lmin[rt<<1], sum[rt<<1] + lmin[rt<<1|1]);
16     rmin[rt] = min(rmin[rt<<1|1], sum[rt<<1|1] + rmin[rt<<1]);
17     tmin[rt] = min(min(tmin[rt<<1], tmin[rt<<1|1]), rmin[rt<<1] + lmin[rt<<1|1]);
18 }
19 void build(int l,int r,int rt)
20 {
21     if (l == r)
22     {
23         scanf("%d",&sum[rt]);
24         lmax[rt] = rmax[rt] = tmax[rt] = lmin[rt] = rmin[rt] = tmin[rt] = sum[rt];
25         return;
26     }
27     int m = (l + r) >> 1;
28     build(lson);
29     build(rson);
30     PushUp(rt);
31 }
32 void update(int a,int b,int l,int r,int rt)
33 {
34     if (l == r && l == a)
35     {
36         lmax[rt] = rmax[rt] = tmax[rt] = lmin[rt] = rmin[rt] = tmin[rt] = sum[rt] = b;
37         return;
38     }
39     int m = (l + r) >> 1;
40     if (a <= m) update(a, b, lson);
41     else update(a, b, rson);
42     PushUp(rt);
43 }
44 int main()
45 {
46     int n, m;
47     //freopen("data.in","r",stdin);
48     scanf("%d",&n);
49     build(1, n, 1);
50     scanf("%d",&m);
51     while (m--)
52     {
53         int a, b;
54         scanf("%d%d",&a,&b);
55         update(a, b, 1, n, 1);
56         if (sum[1] == tmax[1]) printf("%d\n",sum[1] - tmin[1]);
57         else printf("%d\n",max(tmax[1], sum[1] - tmin[1]));
58     }
59     return 0;
60 }

POJ 2750 Potted Flower 线段树区间合并

推荐阅读