Solution

线段树是一门比较刁钻的手艺...

此题我们需要维护 \(4\) 个变量:

1. \(amx\) 代表当前节点的最大值.
2. \(lmx\) 代表当前节点以左端点为起点的区间最大值.
3. \(rmx\) 代表当前节点以右端点为结尾的区间最大值.
4. \(sum\) 代表整段的和.

然后我们在 \(push\)_\(up\) 的时候,也是要做蛮多工作.

\(lc\) 为左端点,\(rc\) 为右端点.

1. \(lmx=max(lmx_{lc},sum_{lc}+lmx_{rc})\)

   也就是说可以单独取左儿子里的最大值,也可以一直取到右儿子的 \(lmx\) 为止.

2. \(rmx=max(rmx_{rc},sum_{rc}+rmx_{lc})\)
   和上文同理.
3. \(sum=sum_{lc}+sum_{rc}\)

4. \(amx=max(amx_{lc},amx_{rc},rmx_{lc}+lmx_{rc})\)

   最关键的一步,更新每一个节点的答案. 可以在图上自己理解,此处不赘述.

特别注意,查询的时候也要把所有查出来的区间进行类似的操作...

Code

#include
    
     using namespace std;const int maxn=1000008;struct node{    int l,r,lc,rc;    int lmx,rmx,amx,sum;}sgm[maxn*4];int n,m,k,x,y;int cnt,a[maxn];void push_up(int x){    int ll=sgm[x].lc,rr=sgm[x].rc;    sgm[x].sum=sgm[ll].sum+sgm[rr].sum;    sgm[x].lmx=max(sgm[ll].lmx,sgm[ll].sum+sgm[rr].lmx);    sgm[x].rmx=max(sgm[rr].rmx,sgm[rr].sum+sgm[ll].rmx);    sgm[x].amx=max(max(sgm[ll].amx,sgm[rr].amx),sgm[ll].rmx+sgm[rr].lmx);}void build(int l,int r,int now){    sgm[now].l=l;    sgm[now].r=r;    if(l==r)    {        sgm[now].lmx=sgm[now].rmx=sgm[now].sum=sgm[now].amx=a[l];        return;    }    int mid=(l+r)>>1;    sgm[now].lc=2*now;    build(l,mid,sgm[now].lc);    sgm[now].rc=2*now+1;    build(mid+1,r,sgm[now].rc);    push_up(now);}void change(int now,int to,int num){    int x=sgm[now].l,y=sgm[now].r;    if(x==y)    {        sgm[now].lmx=sgm[now].rmx=sgm[now].sum=sgm[now].amx=num;        return;    }    int mid=(x+y)>>1;    if(to<=mid) change(sgm[now].lc,to,num);    else change(sgm[now].rc,to,num);    push_up(now);}node query(int now,int l,int r){    int x=sgm[now].l,y=sgm[now].r;    if(l<=x&&r>=y) return sgm[now];    int mid=(x+y)>>1,ll=sgm[now].lc,rr=sgm[now].rc;    if(r<=mid) return query(ll,l,r);    else if(l>mid) return query(rr,l,r);    else    {        node t,t1=query(ll,l,r),t2=query(rr,l,r);        t.lmx=max(t1.lmx,t1.sum+t2.lmx);        t.rmx=max(t2.rmx,t2.sum+t1.rmx);        t.amx=max(max(t1.amx,t2.amx),t1.rmx+t2.lmx);        return t;    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    build(1,n,1);    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&k,&x,&y);        if(k==1)         {            if(x>y) swap(x,y);            printf("%d\n",query(1,x,y).amx);        }        else change(1,x,y);    }    return 0;}