SPOJ GSS3-Can you answer these queries III-分治+线段树区间合并

Can you answer these queries III

SPOJ - GSS3 

这道题和洛谷的小白逛公园一样的题目。

传送门：

洛谷 P4513 小白逛公园-区间最大子段和-分治+线段树区间合并(单点更新、区间查询)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+10;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct Tree{
    int pre,suf,sub,val;
}tree[maxn<<2];

Tree pushup(Tree l,Tree r)
{
    Tree rt;
    rt.pre=max(l.pre,l.val+r.pre);
    rt.suf=max(r.suf,r.val+l.suf);
    rt.sub=max(max(l.sub,r.sub),l.suf+r.pre);
    rt.val=l.val+r.val;
    return rt;
}

void build(int l,int r,int rt)
{
    if(l==r){
        scanf("%d",&tree[rt].val);
        tree[rt].pre=tree[rt].suf=tree[rt].sub=tree[rt].val;
        return ;
    }

    int m=(l+r)>>1;
    build(lson);
    build(rson);
    tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]);
}

void update(int pos,int c,int l,int r,int rt)
{
    if(l==r){
        tree[rt].pre=tree[rt].suf=tree[rt].sub=tree[rt].val=c;
        return ;
    }

    int m=(l+r)>>1;
    if(pos<=m) update(pos,c,lson);
    if(pos> m) update(pos,c,rson);
    tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]);
}

Tree query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R){
        return tree[rt];
    }

    int m=(l+r)>>1;
    Tree ret,lret,rret;
    int flag1=0,flag2=0;
    if(L<=m) {lret=query(L,R,lson);flag1=1;}
    if(R> m) {rret=query(L,R,rson);flag2=1;}

    if(flag1&&flag2) ret=pushup(lret,rret);
    else if(flag1) ret=lret;
    else if(flag2) ret=rret;
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    build(1,n,1);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==0){
            update(l,r,1,n,1);
        }
        else{
            Tree ans=query(l,r,1,n,1);
            printf("%d\n",ans.sub);
        }
    }
    return 0;
}