线段树60pts求调

rt

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N,M,w[4000005];
struct SegTree{
    struct node{
        LL L,R,ls,rs;
        LL Max,setv=-99999999999,addv=0;
    }a[5000005];
    LL ls(LL p){return a[p].ls;}
    LL rs(LL p){return a[p].rs;}
    void pushup(LL p)
    {a[p].Max=max(a[ls(p)].Max,a[rs(p)].Max);}
    void pushdown(LL p){
        if(a[p].setv!=-99999999999){
            a[ls(p)].setv=a[rs(p)].setv=a[p].setv;
            a[ls(p)].Max=a[ls(p)].Max=a[p].setv;
            a[p].setv=-99999999999;
        }
        if(a[p].addv){
            a[ls(p)].addv+=a[p].addv;a[rs(p)].addv+=a[p].addv;
            a[ls(p)].Max+=a[p].addv;a[rs(p)].Max+=a[p].addv;
            a[p].addv=0;
        }
    }
    void build(LL p,LL L,LL R){
        a[p].L=L;a[p].R=R;
        if(L==R)
        {a[p].Max=w[L];return;}
        LL mid=(L+R)>>1;
        a[p].ls=(p<<1);a[p].rs=(p<<1|1);
        build(a[p].ls,L,mid);build(a[p].rs,mid+1,R);
        pushup(p);
        return;
    }
    void Set(LL p,LL ql,LL qr,LL X){
        LL L=a[p].L,R=a[p].R;
        if(ql<=L&&R<=qr)
        {a[p].Max=X;a[p].setv=X;a[p].addv=0;return;}
        pushdown(p);
        LL mid=(L+R)>>1;
        if(ql<=mid)Set(ls(p),ql,qr,X);
        if(mid+1<=qr)Set(rs(p),ql,qr,X);
        pushup(p);
        return;
    }
    void Add(LL p,LL ql,LL qr,LL X){
        LL L=a[p].L,R=a[p].R;
        if(ql<=L&&R<=qr)
        {a[p].Max+=X;a[p].addv+=X;return;}
        pushdown(p);
        LL mid=(L+R)>>1;
        if(ql<=mid)Add(ls(p),ql,qr,X);
        if(mid+1<=qr)Add(rs(p),ql,qr,X);
        pushup(p);
        return;
    }
    LL query(LL p,LL ql,LL qr){
        LL L=a[p].L,R=a[p].R;
        if(ql<=L&&R<=qr){return a[p].Max;}
        pushdown(p);
        LL mid=(L+R)>>1,ret=-5e18;
        if(ql<=mid)ret=max(ret,query(ls(p),ql,qr));
        if(mid+1<=qr)ret=max(ret,query(rs(p),ql,qr));   
        return ret;
    }
}Tree;
int main(){
    scanf("%lld%lld",&N,&M);
    for(int i=1;i<=N;i++)
        scanf("%lld",&w[i]);
    Tree.build(1,1,N);
    while(M--){
        LL op,l,r,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;Tree.Set(1,l,r,x);
        }else if(op==2){
            cin>>x;Tree.Add(1,l,r,x);
        }else if(op==3){
            cout<<Tree.query(1,l,r)<<endl;
        }   
    }
    return 0;
}