9pts线段树求调+悬关

#include<bits/stdc++.h>
#define rm (x*2+1)
#define lm (x*2)
#define mid ((l+r)/2)
#define ll long long
using namespace std;
const ll N=3e6+5;
ll sum[N],n,m,a[N],rl[N],lr[N],ans[N];
void update(ll x)
{
    sum[x]=sum[lm]+sum[rm];
    rl[x]=max(rl[rm],sum[rm]+rl[lm]);
    lr[x]=max(lr[lm],sum[lm]+lr[rm]);
    ans[x]=max(max(ans[lm],ans[rm]),rl[lm]+lr[rm]);
}
void build(ll x,ll l,ll r)
{
    if(l==r)
    {
        sum[x]=rl[x]=lr[x]=ans[x]=a[l];
        return ;
    }
    build(lm,l,mid);
    build(rm,mid+1,r);
    update(x);
}
void add(ll x,ll l,ll r,ll k,ll kk)
{
    if(l==r)
    {
        a[l]=sum[x]=rl[x]=lr[x]=ans[x]=kk;
        return ;
    }
    if(k>mid) add(rm,mid+1,r,k,kk);
    else add(lm,l,mid,k,kk);
    update(x);
}
ll fans[N],cnt;
void find(ll x,ll l,ll r,ll L,ll R)
{
    if(l>=L&&r<=R) 
    {
        fans[++cnt]=x;
        return ;
    }
    if(L<=mid) find(lm,l,mid,L,mid);
    if(R>mid) find(rm,mid+1,r,mid+1,R);
}
int main()
{
//  cout<<"dongruoqi\n";
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        ll p;
        cin>>p;
        if(p==1)
        {
            ll xx,yy;
            cin>>xx>>yy;
            if(xx>yy) swap(xx,yy);
            cnt=0;
            find(1,1,n,xx,yy);
            ll summ=sum[fans[1]],rll=rl[fans[1]],lrr=lr[fans[1]],anss=ans[fans[1]];
            for(ll i=2;i<=cnt;i++)
            {
                anss=max(anss,max(ans[fans[i]],rll+lr[fans[i]]));
                rll=max(rl[fans[i]],rll+sum[fans[i]]);
                lrr=max(lrr,summ+lr[fans[i]]);
                summ=summ+sum[fans[i]];
            }
            cout<<anss<<"\n";
        }
        else
        {
            ll pp,s;
            cin>>pp>>s;
            add(1,1,n,pp,s);
        }
    }
    return 0;
}