WA9分求条

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
const ll ninf=LLONG_MIN;
int n,m;
ll a[500002];
struct node{
    int l,r;
    ll ls,rs,s,mxs;
}tr[2000002];
inline bool in(int l,int r,int L,int R){return L<=l&&r<=R;}
inline bool out(int l,int r,int L,int R){return r<L||R<l;}
void pup(int u){
    tr[u].ls=max(tr[2*u].ls,tr[2*u].s+tr[2*u+1].ls);
    tr[u].rs=max(tr[2*u+1].rs,tr[2*u+1].s+tr[2*u].rs);
    tr[u].s=tr[2*u].s+tr[2*u+1].s;
    tr[u].mxs=max({tr[2*u].mxs,tr[2*u+1].mxs,tr[2*u].rs+tr[2*u+1].ls});
}
void build(int u,int l,int r){
    tr[u].l=l;
    tr[u].r=r;
    if(l==r){
        tr[u].ls=tr[u].rs=tr[u].s=tr[u].mxs=a[l];
        return;
    }
    int m=(l+r)/2;
    build(2*u,l,m);
    build(2*u+1,m+1,r);
    pup(u);
}
void change(int u,int p,ll s){
    if(tr[u].l==tr[u].r){
        tr[u].ls=tr[u].rs=tr[u].s=tr[u].mxs=s;
        return;
    }
    if(u<=tr[2*u].r) change(2*u,p,s);
    else change(2*u+1,p,s);
    pup(u);
}
array<ll,4> qry(int u,int l,int r){
    if(in(tr[u].l,tr[u].r,l,r)) return array<ll,4>({tr[u].ls,tr[u].rs,tr[u].s,tr[u].mxs});
    else if(!out(tr[u].l,tr[u].r,l,r)){
        array<ll,4> lk=qry(2*u,l,r),rk=qry(2*u+1,l,r);
        if(lk[0]==ninf) return rk;
        if(rk[0]==ninf) return lk;
        return array<ll,4>({max(lk[0],lk[2]+rk[0]),max(rk[1],rk[2]+lk[1]),
                            lk[2]+rk[2],max({lk[3],rk[3],lk[1]+rk[0]})});
    }else return array<ll,4>({ninf,ninf,ninf,ninf});
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        int k;
        scanf("%d",&k);
        if(k==1){
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>b) swap(a,b);
            printf("%lld\n",qry(1,a,b)[3]);
        }else{
            int p;
            ll s;
            scanf("%d%lld",&p,&s);
            change(1,p,s);
        }
    }
    return 0;
}