dango

POJ2750 Potted Flower(线段树区间更新)

传送门： http://poj.org/problem?id=2750

题目大意：
一堆花围成一圈，每一盆都有自己的attractive value。要你来选一串花，使得总attractive value最大。（题目中有一个非常重要的条件：不可以选所有的花，这个一不注意就功亏一篑了）
每次，有一只坏猫会来把第A盆花的attractive value换成B。坏猫每捣蛋一次，你就要求一个新的总attractive value最大的连续序列。

解题思路：
数据那么大，暴力搞肯定超时了，这种区间最大最小值的问题首先还是应该要想到线段树的。

1 struct tnode 
2 {
3     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
4     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
5     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
6     //int minn;           //当前区间最大最小值 
7 }t[maxn*4];

线段树的节点定下来以后写法差不多也就定了。
每次需要根据孩子的情况来更新父节点的各种值。判断的时候一定要把“转移”（这个挺像动态规划的状态转移的其实……）情况都想齐全，再下手写，写的时候比较容易晕，一定要仔细，避免查错的时候头昏脑胀。
WA了一次，有一个地方没写好。题中说不可以选取所有的花，所以若得到的总attractive value最大的连续序列是整圈的花，就要剪掉整圈花总attractive value最小的连续序列的attractive value和，WA的时候之剪了最小attractive value的一盆花。

代码：（注释掉的一些地方是第一次错的地方，引以为戒~）

POJ2750
 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define maxn 100010
 4 
 5 struct tnode 
 6 {
 7     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
 8     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
 9     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
10     //int minn;           //当前区间最大最小值 
11 }t[maxn*4];
12 
13 int data[maxn];// 存放输入数据 
14 int n,m;// 点数、修改次数 
15 
16 int min(int a, int b, int c, int d, int e){
17     int ret=(a<b)?a:b;
18     ret=(ret<c)?ret:c;
19     ret=(ret<d)?ret:d;
20     ret=(ret<e)?ret:e;
21     return ret;
22 }
23 int max(int a, int b, int c, int d, int e){
24     int ret=(a>b)?a:b;
25     ret=(ret>c)?ret:c;
26     ret=(ret>d)?ret:d;
27     ret=(ret>e)?ret:e;
28     return ret;
29 }
30 int min2(int a, int b){
31     if (a<b) return a; else return b;
32 }
33 int max2(int a, int b){
34     if (a>b) return a; else return b;
35 }
36 
37 void update(int k){
38     int lson=k<<1, rson=(k<<1)+1;
39     t[k].sum = t[lson].sum+t[rson].sum;
40     t[k].lmax = max2(t[lson].sum+t[rson].lmax, t[lson].lmax);
41     t[k].lmin = min2(t[lson].sum+t[rson].lmin, t[lson].lmin);
42     t[k].rmax = max2(t[rson].sum+t[lson].rmax, t[rson].rmax);
43     t[k].rmin = min2(t[rson].sum+t[lson].rmin, t[rson].rmin);
44     t[k].mins=min(t[lson].mins, t[rson].mins,
45                   t[lson].rmin+t[rson].lmin, t[k].rmin, t[k].lmin);
46     t[k].maxs=max(t[lson].maxs, t[rson].maxs, 
47                   t[lson].rmax+t[rson].lmax, t[k].rmax, t[k].lmax);
48     //t[k].minn= min2(t[lson].minn, t[rson].minn);
49 }
50 
51 void buildtree(int k, int l, int r){
52     if (l==r){
53         t[k].sum=t[k].mins=t[k].maxs=data[l];
54         t[k].lmin=t[k].rmin=t[k].lmax=t[k].rmax=data[l];
55         //t[k].minn=data[l];
56     }
57     else{
58         int mid=(l+r)>>1;
59         buildtree(k<<1, l, mid);
60         buildtree((k<<1)+1, mid+1, r);
61         update(k);
62     }
63 }
64 
65 void modify(int k, int l, int r, int a, int b){
66     if (l==r){
67         t[k].sum=t[k].mins=t[k].maxs=b;
68         t[k].lmin=t[k].rmin=t[k].lmax=t[k].rmax=b;
69         //t[k].minn=b;
70     }
71     else{
72         int mid=(l+r)>>1;
73         if (a<=mid)
74             modify(k<<1, l, mid, a, b);
75         else
76             modify((k<<1)+1, mid+1, r, a, b);
77         update(k);
78     }
79 }
80 
81 int main(){
82     int ans, a, b;
83     scanf("%d", &n);
84     for (int i=1; i<=n; i++) scanf("%d", &data[i]);
85     buildtree(1, 1, n);
86     scanf("%d", &m);
87     while (m--){
88         scanf("%d%d", &a, &b);
89         modify(1, 1, n, a, b);
90         if (t[1].maxs==t[1].sum)
91             ans=t[1].sum-t[1].mins; //not -t[1].minnumber
92         else
93             ans=max2(t[1].maxs, t[1].sum-t[1].mins); //not -t[1].minnumber
94         printf("%d\n", ans);
95     }
96     system("pause");
97     return 0;
98 }
99