【题解】SPOJ P1716 【GSS3 – Can you answer these queries III】

这里可用线段树做,对于线段树上的每个结点,除区间端点外,再维护4个信息:区间和$sum$,区间最大连续子段和$data$,紧靠左端点的最大连续子段和$lmax$,紧靠右端点的最大连续子段和$rmax$。

线段树整体框架不变,只需在$build$和$change$函数中从下往上传递信息:

$t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;$
$t[p].lmax = \max (t[LEFT(p)].lmax,t[LEFT(p)].sum + t[RIGHT(p)].lmax);$
$t[p].rmax = \max (t[RIGHT(p)].rmax,t[RIGHT(p)].sum + t[LEFT(p)].rmax);$
$t[p].data = \max (t[LEFT(p)].data,t[RIGHT(p)].data,t[LEFT(p)].rmax + t[RIGHT(p)].lmax);$

 

#include<cstdio>

const int MAXN = 50000 + 6;
int A[MAXN];

class SegmentTree{
    public:int l,r;
    public:int sum,data,lmax,rmax;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}
inline int max(int a,int b){return a > b ? a : b;}
inline int max(int a,int b,int c){return max(max(a,b),c);}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].sum = t[p].data = t[p].lmax = t[p].rmax = A[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
    t[p].lmax = max(t[LEFT(p)].lmax,t[LEFT(p)].sum + t[RIGHT(p)].lmax);
    t[p].rmax = max(t[RIGHT(p)].rmax,t[RIGHT(p)].sum + t[LEFT(p)].rmax);
    t[p].data = max(t[LEFT(p)].data,t[RIGHT(p)].data,t[LEFT(p)].rmax + t[RIGHT(p)].lmax);
}

void change(int p,int x,int v){
    if(t[p].l == t[p].r){
        t[p].sum = t[p].data = t[p].lmax = t[p].rmax = v;
        return;
    }
    if(x <= MID(t[p].l,t[p].r)){
        change(LEFT(p),x,v);
    }else{
        change(RIGHT(p),x,v);
    }
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
    t[p].lmax = max(t[LEFT(p)].lmax,t[LEFT(p)].sum + t[RIGHT(p)].lmax);
    t[p].rmax = max(t[RIGHT(p)].rmax,t[RIGHT(p)].sum + t[LEFT(p)].rmax);
    t[p].data = max(t[LEFT(p)].data,t[RIGHT(p)].data,t[LEFT(p)].rmax + t[RIGHT(p)].lmax);
}

SegmentTree ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p];
    }
    SegmentTree g,gg;
    if(l > MID(t[p].l,t[p].r)){
        return ask(RIGHT(p),l,r);
    }else if(r <= MID(t[p].l,t[p].r)){
        return gg = ask(LEFT(p),l,r);
    }else{
        g = ask(LEFT(p),l,r);
        gg = ask(RIGHT(p),l,r);
        SegmentTree ans;
        ans.data = max(g.data,gg.data,g.rmax + gg.lmax);
        ans.lmax = max(g.lmax,g.sum + gg.lmax);
        ans.rmax = max(gg.rmax,gg.sum + g.rmax);
        return ans;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&A[i]);
    }
    
    build(1,1,n);
    
    int q;
    scanf("%d",&q);
    
    while(q--){
        int op,x,y;
        scanf("%d %d %d",&op,&x,&y);
        
        if(op == 0){
            change(1,x,y);
        }else{
            printf("%d\n",ask(1,x,y).data);
        }
    }
    
    return 0;
}