得了一种看到高级数据结构就害怕的病

但我们还是要迎♂而上（雾

题意：有n个数，a[1]到a[n]。接下来q次操作，一种是将a[x]变为y，另一种是指定两个数l,r，求a[l]到a[r]的最大子段和。

思路：

gss的维护上面说到了；

lgss的维护：

1.左儿子的lgss 2.左儿子的sum+右儿子的lgss（如果跨过了左儿子区间，左边最长连续区间肯定要取到左区间的sum）。

rgss的维护：

1.右儿子的rgss 2.右儿子的sum+左儿子的rgg。

询问：

利用先遍历左儿子的性质。

ans：1.该区间的gss 2.之前所有区间的最大字段和+该区间的lgss。

所以设置一个变量pre用来记录之前所有区间的最大字段和。

pre的维护：1.该区间的rgss 2.pre+该区间的sum。

代码：

#define INF 0x3f3f3f3f
#define nl id<<1
#define nr id<<1|1
struct Node
{
    int left,right;
    int sum;//区间和
    int gss;//最大子段和
    int lgss,rgss;//最大左右子段和
}node[50000<<2];
int ans,pre;
void up(int id)
{
    node[id].sum=node[nl].sum+node[nr].sum;
    node[id].gss=max(max(node[nl].gss,node[nr].gss),node[nl].rgss+node[nr].lgss);
    node[id].lgss=max(node[nl].lgss,node[nl].sum+node[nr].lgss);
    node[id].rgss=max(node[nr].rgss,node[nr].sum+node[nl].rgss);
}
void build(int l,int r,int id)
{
    node[id].left=l;node[id].right=r;
    if(l==r)
    {
        scanf("%d",&node[id].sum);
        node[id].lgss=node[id].rgss=node[id].gss=node[id].sum;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,nl);build(m+1,r,nr);
    up(id);
}
void update(int loc,int c,int id)
{
    int l=node[id].left;int r=node[id].right;
    if(l==r)
    {
        node[id].sum=c;
        node[id].lgss=node[id].rgss=node[id].gss=node[id].sum;
        return;
    }
    int m=(l+r)>>1;
    if(loc<=m)update(loc,c,nl);
    else update(loc,c,nr);
    up(id);
}
void query(int L,int R,int id)
{
    int l=node[id].left;int r=node[id].right;
    if(l>=L&&r<=R)
    {
        ans=max(ans,max(node[id].gss,pre+node[id].lgss));
        pre=max(node[id].rgss,pre+node[id].sum);//之前所有区间的最大右字段和
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)query(L,R,nl);
    if(R>m)query(L,R,nr);
}
int main()
{
    int n,q,ope,x,y;
    scanf("%d",&n);
    build(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d",&ope,&x,&y);
        if(ope==0)update(x,y,1);
        else if(ope==1)
        {
            ans=-INF;
            pre=-INF;
            query(x,y,1);
            printf("%d\n",ans);
        }
    }
    return 0;
}