9pts线段树+求调+悬关+码风良好

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N];
int op,x,y;
struct node{
    int sum,w;
    int lmx,rmx;
}t[4*N];
void pushup(int u){
    t[u].w=t[u*2].w+t[u*2+1].w;
    t[u].lmx=max(t[u*2].lmx,t[u*2].w+t[u*2+1].lmx);
    t[u].rmx=max(t[u*2+1].rmx,t[u*2+1].w+t[u*2].rmx);
    t[u].sum=max(t[u*2].sum,t[u*2+1].sum);
    t[u].sum=max(t[u].sum,t[u*2].sum+t[u*2+1].sum);
}
void build(int u,int l,int r){
    if(l==r){
        t[u].lmx=t[u].rmx=a[l];
        t[u].sum=t[u].w=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
void upd(int u,int l,int r,int p,int x){
    if(l==r){
        t[u].lmx=t[u].rmx=x;
        t[u].sum=t[u].w=x;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)upd(u*2,l,mid,p,x);
    else upd(u*2+1,mid+1,r,p,x);
    pushup(u);
}
node qry(int u,int L,int R,int l,int r){
    if(l<=L&&R<=r)return t[u];
    int mid=(L+R)>>1;
    if(r<=mid)return qry(u*2,L,mid,l,r);
    else if(mid<l)return qry(u*2+1,mid+1,R,l,r);
    node t,t1,t2;
    t1=qry(u*2,L,mid,l,r);
    t2=qry(u*2+1,mid+1,R,l,r);
    t.lmx=max(t1.lmx,t1.w+t2.lmx);
    t.rmx=max(t2.rmx,t2.w+t1.rmx);
    t.sum=max(max(t1.sum,t2.sum),(t2.lmx+t1.rmx));
    return t;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        cin>>op>>x>>y;
        if(op==1){
            if(x>y)swap(x,y);
            cout<<qry(1,1,n,x,y).sum<<"\n";
        }
        else upd(1,1,n,x,y);
    }
    return 0;
}