60分求调

#include<bits/stdc++.h>
using i64=long long;

const int N=1e6+10;
const i64 INF=1e18;
int n,m;
i64 a[N];

struct Segment{
    int l,r;
    i64 maxn,add,modify=1e18;//add是加法的延迟标记,modify是区间更改的延迟标记
    #define l(x) seg[x].l
    #define r(x) seg[x].r
    #define maxn(x) seg[x].maxn
    #define add(x) seg[x].add
    #define modify(x) seg[x].modify
}seg[4*N];

void build(int p,int l,int r){
    l(p)=l;r(p)=r;
    if(l==r){//叶子结点
        maxn(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    maxn(p)=std::max( maxn(p<<1),maxn(p<<1|1) );
}

void spread(int p){//下放延迟标记,注意优先级问题

    if(add(p)){
        maxn(p<<1)+=add(p);
        maxn(p<<1|1)+=add(p);
        add(p<<1)+=add(p);
        add(p<<1|1)+=add(p);
        add(p)=0;
    }
    if(modify(p)!=INF){
        maxn(p<<1)=modify(p);
        maxn(p<<1|1)=modify(p);
        modify(p<<1)=modify(p);
        modify(p<<1|1)=modify(p);
        add(p<<1)=0;
        add(p<<1|1)=0;
        modify(p)=1e18;
    }
}

void rangeAdd(int p,int l,int r,int k){//区间更新
    if(l<=l(p)&&r>=r(p)){//注意是要查询的区间[l,r]里包含当前结点代表的区间
        maxn(p)+=k;
        add(p)+=k;//别忘了打延迟标记
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    if(l<=mid)
        rangeAdd(p<<1,l,r,k);
    if(r>mid)
        rangeAdd(p<<1|1,l,r,k);
    maxn(p)=std::max(maxn(p<<1),maxn(p<<1|1));
}

void rangeModify(int p,int l,int r,int k){
    if(l<=l(p)&&r>=r(p)){//注意是要查询的区间[l,r]里包含当前结点代表的区间
        maxn(p)=k;
        modify(p)=k;
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    if(l<=mid)
        rangeModify(p<<1,l,r,k);
    if(r>mid)
        rangeModify(p<<1|1,l,r,k);
    maxn(p)=std::max(maxn(p<<1),maxn(p<<1|1));
}

i64 rangeQuery(int p,int l,int r){
    if(l<=l(p)&&r>=r(p))//完全包括
        return maxn(p);
    spread(p);
    i64 ans=-1e18;
    int mid=(l(p)+r(p))>>1;
    if(l<=mid)
        ans=std::max(ans,rangeQuery(p<<1,l,r));
    if(r>mid)
        ans=std::max(ans,rangeQuery(p<<1|1,l,r));
    return ans;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
        std::cin>>a[i];
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        std::cin>>op;
        if(op==1){
            std::cin>>x>>y>>k;
            rangeModify(1,x,y,k);
        }
        else if(op==2){
            std::cin>>x>>y>>k;
            rangeAdd(1,x,y,k);
        }
        else{
            std::cin>>x>>y;
            std::cout<<rangeQuery(1,x,y)<<"\n";
        }
    }
    return 0;
}