萌新求助

再发一次，希望别再沉了。。。

#include <bits/stdc++.h>
using namespace std;
#define ll(x) x*2
#define rr(x) x*2+1
#define lt long long
lt n,m,sen[500005],sgm[2005005],L[2005005],R[2005005],Max[2005005],flag,lx,rx,ans,lans,rans;
inline lt read()
{
    char ch=getchar();lt f=1,w=0;
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){w=w*10+ch-48;ch=getchar();}
    return f*w;
}
inline void hb(lt node){
    Max[node]=max(max(Max[ll(node)],Max[rr(node)]),R[ll(node)]+L[rr(node)]);
    L[node]=max(L[ll(node)],sgm[ll(node)]+L[rr(node)]);
    R[node]=max(R[rr(node)],sgm[rr(node)]+R[ll(node)]);
    sgm[node]=sgm[ll(node)]+sgm[rr(node)];
    return;
}
inline void build(lt node,lt left,lt right){
    if(left>right) return;
    if(left==right)
    {
        Max[node]=sgm[node]=L[node]=R[node]=sen[left];return;
    }
    lt dist=(left+right)>>1;
    build(ll(node),left,dist);
    build(rr(node),dist+1,right);
    hb(node);
    return;
}
inline void insert(lt node,lt left,lt right,lt l,lt r,lt v){
    if(left==right)
    {
        Max[node]=sgm[node]=L[node]=R[node]=v;return;
    }
    lt dist=(left+right)>>1;
    if(r<=dist) insert(ll(node),left,dist,l,r,v);
    else insert(rr(node),dist+1,right,l,r,v);
    hb(node);
    return;
}
inline void check(lt node,lt left,lt right,lt l,lt r,lt &ans,lt &lans,lt &rans)
{
    if(left>r||right<l) return;
    if(left>=l&&right<=r){
        ans=Max[node];lans=L[node];rans=R[node];return;
    }
    lt dist=(left+right)>>1;
    if(r<=dist) check(ll(node),left,dist,l,r,ans,lans,rans);
    else if(l>dist) check(rr(node),dist+1,right,l,r,ans,lans,rans);
    else
    {
        lt Lans,Llans,Lrans,Rans,Rlans,Rrans;
        Lans=Llans=Lrans=Rans=Rlans=Rrans=0;
        check(ll(node),left,dist,l,r,Lans,Llans,Lrans);
        check(rr(node),dist+1,right,l,r,Rans,Rlans,Rrans);
        ans=max(max(Lans,Rans),Lrans+Rlans);
        lans=max(lans,sgm[ll(node)]+Rlans);
        rans=max(rans,sgm[rr(node)]+Lrans);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    n=read();m=read();
    for(lt i=1;i<=n;++i){sen[i]=read();}
    build(1,1,n);
    for(lt i=1;i<=m;++i){
        flag=read();lx=read();rx=read();
        if(flag==1)
        {
            if(lx>rx) swap(lx,rx);
            ans=lans=rans=0;
            check(1,1,n,lx,rx,ans,lans,rans);
            cout<<ans<<endl;
        }
        else
        {
            insert(1,1,n,lx,lx,rx);
        }
    }
    return 0;
}