9ptsWA线段树蒟蒻玄关（指调A就关注）求调

#define INF -1000000000 
#include<iostream>
using namespace std;
const int maxn=505000;
int n,m,a[maxn],opt,x,y;
struct node{
    int l,r,lsum,rsum,sum,all;
}smt[maxn<<2];
struct s{
    int lsum,rsum,sum,all;
};
inline s smax(s a,s b){
    return {max(a.lsum,a.all+b.lsum),max(b.rsum,b.all+a.rsum),max(max(a.sum,b.sum),a.rsum+b.lsum),a.all+b.all};
}
inline void fz(s c,node d){
    c.lsum=d.lsum,c.rsum=d.rsum,c.sum=d.sum,c.all=d.all;
} 
inline void fu(node c,s d){
    c.lsum=d.lsum,c.rsum=d.rsum,c.sum=d.sum,c.all=d.all;
}
#define ll smt[now].l
#define rr smt[now].r
#define mid (ll+rr>>1)
#define s1 smt[now].lsum
#define s2 smt[now].rsum
#define s3 smt[now].sum
#define s4 smt[now].all
#define lson smt[now<<1]
#define rson smt[now<<1^1]
inline void pushup(int now){
    s sa,sb;fz(sa,lson);fz(sb,rson);
    s sc=smax(sa,sb);fu(smt[now],sc);
}
void build(int now){
    if(ll==rr){
        s1=s2=s3=s4=a[ll];return;
    }
    lson.l=ll,rson.r=rr,lson.r=mid,rson.l=mid+1;
    build(now<<1);build(now<<1^1);pushup(now);
}
void change(int now,int k,int val){
    if(ll==rr){
        s1=s2=s3=s4=val;return;
    }
    if(k<=mid)change(now<<1,k,val);
    else change(now<<1^1,k,val);
    pushup(now);
}
s check(int now,int l,int r){
    if(l==ll&&r==rr)return {s1,s2,s3,s4};
    s c={INF,INF,INF,INF},d={INF,INF,INF,INF};
    if(l<=mid)c=check(now<<1,l,min(mid,r));
    if(r>mid)d=check(now<<1^1,max(mid+1,l),r);
    if(c.sum>-9e8&&d.sum>-9e8)return smax(c,d);
    if(l<=mid)return c;return d;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    smt[1].l=1;smt[1].r=n;build(1);
    for(int i=1;i<=m;i++){
        cin>>opt>>x>>y;
        if(opt==1){if(x<=y)cout<<check(1,x,y).sum<<"\n";else cout<<check(1,y,x).sum<<"\n";}
        else change(1,x,y);
    }
    return 0;
}