分块60ptsWA7~10无超时，讨论区的hack都能过

调的心力交瘁了，求调，给Hack也行，玄关。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MINF=-9223372036854775808;//最小值
const int N=2e6+15,T=1500;
int n,m,a[N];
int block,t,pos[N],st[T],ed[T],mx[T];
int add1[T],add2[T];//1是区间赋值，2是区间增加
bool is1[T],is2[T];//is1和is2表示有无标记（因为标记可能为0）
void rebuild(int p){//维护最大值
    if(is1[p])mx[p]=add1[p];//如果被覆盖
    else{
        mx[p]=MINF;
        for(int i=st[p];i<=ed[p];i++)mx[p]=max(mx[p],a[i]+add2[p]);//mx[p]维护的是块内最大值（包括增量）
    }
}
void build(){
    block=sqrt(n);
    t=n/block;
    if(n%block)t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1;
    for(int i=1;i<=t;i++)rebuild(i);
}
void update1(int l,int r,int x){//区间赋值
    int p=pos[l],q=pos[r];
    if(p==q){
        if(is2[p]){//清空标记
            for(int i=st[p];i<=ed[p];i++)a[i]+=add2[p];//暴力下放标记
            is2[p]=0;
            add2[p]=0;
        }
        for(int i=l;i<=r;i++)a[i]=x;//暴力更改
        rebuild(p);//重建
    }else{
        for(int i=p+1;i<=q-1;i++){//覆盖块
            if(is2[i]){//清空标记
                is2[i]=0;
                add2[i]=0;
            }
            is1[i]=1;
            add1[i]=x;
            mx[i]=x;//这里直接更改
        }
        update1(l,ed[p],x);//左散块
        update1(st[q],r,x);//右散块
    }
}
void update2(int l,int r,int x){//区间增加
    int p=pos[l],q=pos[r];
    if(p==q){
        if(is1[p]){//清空标记
            for(int i=st[p];i<=ed[p];i++)a[i]=add1[p];//暴力下放标记
            is1[p]=0;
            add1[p]=0;
        }
        for(int i=l;i<=r;i++)a[i]+=x;//暴力更改
        rebuild(p);
    }else{
        for(int i=p+1;i<=q-1;i++){//增加块
            if(is1[i]){//如果被覆盖，那么区间加后数值也相同，类似于覆盖，直接将覆盖标记加上x
                add1[i]+=x;
                mx[i]=add1[i];
            }
            else{
                is2[i]=1;//否则直接加上增量标记
                add2[i]+=x;
                mx[i]+=x;
            }
        }
        update2(l,ed[p],x);//左散块
        update2(st[q],r,x);//右散块
    }
}
int query(int l,int r){//求最大值
    int p=pos[l],q=pos[r],ans=MINF;
    if(p==q){
        if(is1[p])return add1[p];//如果被覆盖，直接返回覆盖值
        if(is2[p]){for(int i=l;i<=r;i++)ans=max(ans,a[i]+add2[p]);return ans;}
        for(int i=l;i<=r;i++)ans=max(ans,a[i]);return ans;
    }else{
        for(int i=p+1;i<=q-1;i++)ans=max(mx[i],ans);
        ans=max(ans,query(l,ed[p]));
        ans=max(ans,query(st[q],r));
        return ans;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update1(l,r,x);
        }else if(op==2){
            int l,r,x;
            cin>>l>>r>>x;
            update2(l,r,x);
        }else if(op==3){
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }
    }
    return 0;
}