正常线段树做法9pts,求条

#include<bits/stdc++.h>
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int n,m;
struct Tree{
    int lmax,rmax,mmax,val;
}t[maxn*4];
Tree pushup(Tree l,Tree r){
    Tree rt;
    rt.lmax=max(l.lmax,l.val+r.lmax);
    rt.lmax=max(rt.lmax,0);
    rt.rmax=max(r.rmax,r.val+l.rmax);
    rt.rmax=max(rt.rmax,0);
    rt.mmax=max(max(l.mmax,r.mmax),l.rmax+r.lmax);
    // rt.mmax=max(rt.mmax,0);
    rt.val=l.val+r.val;
    return rt;
}
void build(int l,int r,int rt){
    if(l==r){
        cin>>t[rt].val;
        t[rt].lmax=t[rt].rmax=t[rt].mmax=t[rt].val;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    t[rt]=pushup(t[rt*2],t[rt*2+1]);
    return;
}
void update(int pos,int c,int l,int r,int rt){
    if(l==r){
        t[rt].lmax=t[rt].rmax=t[rt].mmax=t[rt].val=c;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(pos,c,lson);
    if(pos>m) update(pos,c,rson);
    t[rt]=pushup(t[rt*2],t[rt*2+1]);
}
Tree query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return t[rt];
    }
    int m=(l+r)/2;
    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(){
    cin>>n>>m;
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==2){
            update(l,r,1,n,1);
        }
        else{
            Tree ans=query(l,r,1,n,1);
            cout<<ans.mmax<<endl;
        }
    }
    return 0;
}