50pts玄关求条

#include<bits/stdc++.h>
#define int long long
#define N 1001000
using namespace std;
int n,m,a[N];
struct Node{
    int maxn,add,tag;
}tree[N<<2];
void build(int rt,int l,int r){
    if(l==r){
        tree[rt]={a[l],0,0};
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tree[rt]={max(tree[rt<<1].maxn,tree[rt<<1|1].maxn),0,0};
}
void pushdown1(int rt,int l,int r){
    tree[rt<<1]={tree[rt].tag+tree[rt].add,tree[rt<<1].add+tree[rt].add,tree[rt].tag};
    tree[rt<<1|1]={tree[rt].tag+tree[rt].add,tree[rt<<1|1].add+tree[rt].add,tree[rt].tag};
    tree[rt]={max(tree[rt<<1].maxn,tree[rt<<1|1].maxn),0,0};
}
void pushdown2(int rt,int l,int r){
    tree[rt<<1]={tree[rt<<1].maxn+tree[rt].add,tree[rt<<1].add+tree[rt].add,tree[rt<<1].tag};
    tree[rt<<1|1]={tree[rt<<1|1].maxn+tree[rt].add,tree[rt<<1|1].add+tree[rt].add,tree[rt<<1|1].tag};
    tree[rt]={max(tree[rt<<1].maxn,tree[rt<<1|1].maxn),0,0};
}
int query(int rt,int l,int r,int x,int y){
    if(x<=l and r<=y)return tree[rt].maxn;
    if(tree[rt].tag)pushdown1(rt,l,r);
    else if(tree[rt].add)pushdown2(rt,l,r);
    int mid=(l+r)>>1;
    int res=-1e18;
    if(x<=mid)res=max(res,query(rt<<1,l,mid,x,y));
    if(y>mid)res=max(res,query(rt<<1|1,mid+1,r,x,y));
    return res;
}
void modify1(int rt,int l,int r,int x,int y,int k){
    if(r<=y and l>=x){
        tree[rt]={k,0,k};
        return ;
    }
    if(tree[rt].tag)pushdown1(rt,l,r);
    else if(tree[rt].add)pushdown2(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify1(rt<<1,l,mid,x,y,k);
    if(y>mid)modify1(rt<<1|1,mid+1,r,x,y,k);
    tree[rt]={max(tree[rt<<1].maxn,tree[rt<<1|1].maxn),0,0};
}
void modify2(int rt,int l,int r,int x,int y,int k){
    if(r<=y and l>=x){
        tree[rt]={tree[rt].maxn+k,tree[rt].add+k,tree[rt].tag};
        return ;
    }
    if(tree[rt].tag)pushdown1(rt,l,r);
    else if(tree[rt].add)pushdown2(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify2(rt<<1,l,mid,x,y,k);
    if(y>mid)modify2(rt<<1|1,mid+1,r,x,y,k);
    tree[rt]={max(tree[rt<<1].maxn,tree[rt<<1|1].maxn),0,0};
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            modify1(1,1,n,l,r,x);
        }
        if(op==2){
            int l,r,x;
            cin>>l>>r>>x;
            modify2(1,1,n,l,r,x);
        }
        if(op==3){
            int l,r;
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<"\n";
        }
    }
    return 0;
}