POJ 2750 Potted Flower （單點修改求線段樹上最大子序列和）

POJ 2750 Potted Flower （單點修改求線段樹上最大子序列和）

題目大意：

在一個序列上每次修改一個值，然後求出它的最大的子序列和。

思路分析：

首先我們不考慮不成環的問題。那就是直接求每個區間的最大值就好了。

但是此處成環，那麼看一下下面樣例。

5

1 -2 -3 4 5

那麼你會發現 max = sum - min

也就是和減去最小區間和也可以得到。

所以我們最後要得到的就是兩個東西。注意題目中說的不能全部取得。所以還要判斷一下max 是不是等於 sum的。

#include 
#include 
#include 
#include 
#define maxn 100005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
using namespace std;

struct SegTree
{
    int s,e,sum;
    int lmax,rmax;
    int lmin,rmin;
    int mmin,mmax;
}ret[maxn<<2];

void pushup(int num){
    ret[num].sum=ret[num<<1].sum+ret[num<<1|1].sum;
    ret[num].lmax=max(ret[num<<1].lmax,ret[num<<1].sum+ret[num<<1|1].lmax);
    ret[num].lmin=min(ret[num<<1].lmin,ret[num<<1].sum+ret[num<<1|1].lmin);
    ret[num].rmax=max(ret[num<<1|1].rmax,ret[num<<1|1].sum+ret[num<<1].rmax);
    ret[num].rmin=min(ret[num<<1|1].rmin,ret[num<<1|1].sum+ret[num<<1].rmin);
    ret[num].mmax=max(ret[num<<1].rmax+ret[num<<1|1].lmax,max(ret[num<<1].mmin,ret[num<<1|1].mmin));
    ret[num].mmin=min(ret[num<<1].rmin+ret[num<<1|1].lmin,min(ret[num<<1].mmin,ret[num<<1|1].mmin));
}
void build(int num,int s,int e){
    ret[num].s=s,ret[num].e=e;
    if(s==e){
        scanf("%d",&ret[num].lmax);
        ret[num].sum=ret[num].rmax=ret[num].lmin=ret[num].rmin=ret[num].mmin=ret[num].mmax=ret[num].lmax;
        return;
    }
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
    pushup(num);
}
void update(int num,int s,int e,int pos,int val){
    if(s==e){
        ret[num].sum=ret[num].lmax=ret[num].rmax=ret[num].lmin=ret[num].rmin=ret[num].mmin=ret[num].mmax=val;
        return;
    }
    int mid=(s+e)>>1;
    if(pos<=mid)update(lson,pos,val);
    else update(rson,pos,val);
    pushup(num);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        build(1,1,n);
        int m;
        scanf("%d",&m);
        while(m--){
            int pos,v;
            scanf("%d%d",&pos,&v);
            update(1,1,n,pos,v);
            if(ret[1].mmax!=ret[1].sum)
            printf("%d\n",max(ret[1].mmax,ret[1].sum-ret[1].mmin));
            else printf("%d\n",ret[1].sum-ret[1].mmin);
        }
    }
    return 0;
}