20 分玄关求条

#include <bits/stdc++.h>
#define BAR cout<<"*******\n";
#define fst first
#define snd second
#define INFILE(x) freopen(x,"r",stdin)
#define OUTFILE(x) freopen(x,"w",stdout)
#define eb_ emplace_back
#define ep_ emplace
#define mp_ make_pair
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll=long long;
using ul=unsigned long long;
using ui=unsigned int;
using db=double;
using pii=pair<int,int>;
using pil=pair<int,ll>;
using pll=pair<ll,ll>;
constexpr int int_inf=0x3f3f3f3f;
constexpr ll ll_inf=0x3f3f3f3f3f3f3f3fll;

namespace Solution{
constexpr int max_n=1e6+10;
ll a[max_n];
struct {
    struct node{
        int ls,rs;
        ll val,lazy1,lazy2;
        void init(){
            lazy2=-ll_inf;
        }
    } nodes[2*max_n];
    int tot=0;
    node &root=nodes[0];

    void push_up(node &p){
        p.val=max(nodes[p.ls].val,nodes[p.rs].val);
    }

    void push_down(node &p,int nl,int nr){
        node &ls=nodes[p.ls],&rs=nodes[p.rs];
        if(p.lazy2!=-ll_inf){
            p.lazy2+=p.lazy1;
            p.lazy1=0;
            ls.lazy1=rs.lazy1=0;
            ls.lazy2=rs.lazy2=p.lazy2;
            ls.val=p.lazy2;
            rs.val=p.lazy2;
            p.lazy2=-ll_inf;
        }else if(p.lazy1){
            ls.lazy1+=p.lazy1;
            rs.lazy1+=p.lazy1;
            ls.val+=p.lazy1;
            ls.val+=p.lazy1;
            p.lazy1=0;
        }
    }

    void build(node &p,int nl,int nr){
        p.init();
        if(nl==nr){
            p.val=a[nl];
            return;
        }
        p.ls=++tot;
        p.rs=++tot;
        int mid=(nl+nr)>>1;
        build(nodes[p.ls],nl,mid);
        build(nodes[p.rs],mid+1,nr);
        push_up(p);
    }

    void modify(int l,int r,ll val,node &p,int nl,int nr){
        if(l<=nl&&nr<=r){
            p.lazy1=0;
            p.lazy2=val;
            p.val=val;
            return;
        }
        push_down(p,nl,nr);
        int mid=(nl+nr)>>1;
        if(l<=mid) modify(l,r,val,nodes[p.ls],nl,mid);
        if(r>mid) modify(l,r,val,nodes[p.rs],mid+1,nr);
        push_up(p);
    }

    void add(int l,int r,ll val,node &p,int nl,int nr){
        if(l<=nl&&nr<=r){
            p.lazy1+=val;
            p.val+=val;
            return;
        }
        push_down(p,nl,nr);
        int mid=(nl+nr)>>1;
        if(l<=mid) add(l,r,val,nodes[p.ls],nl,mid);
        if(r>mid) add(l,r,val,nodes[p.rs],mid+1,nr);
        push_up(p);
    }

    ll query(int l,int r,node &p,int nl,int nr){
        if(l<=nl&&nr<=r){
            return p.val;
        }
        push_down(p,nl,nr);
        int mid=(nl+nr)>>1;
        ll ans=-ll_inf;
        if(l<=mid) ans=max(ans,query(l,r,nodes[p.ls],nl,mid));
        if(r>mid) ans=max(ans,query(l,r,nodes[p.rs],mid+1,nr));
        return ans;
    }
} tree;
void solve() {
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    tree.build(tree.root,1,n);
    for(int i=1;i<=q;++i){
        int op,l,r,x;
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            tree.modify(l,r,x,tree.root,1,n);
        }else if(op==2){
            cin>>l>>r>>x;
            tree.add(l,r,x,tree.root,1,n);
        }else if(op==3){
            cin>>l>>r;
            cout<<tree.query(l,r,tree.root,1,n)<<'\n';
        }
    }
}
}

int main() {
    //INFILE("IOFile/P1253_2.in");
    //freopen("IOFile/P1253_2.my.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        Solution::solve();
    }
    return 0;
}