WA50，求调

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int M=405;
const long long inf=1e18;
typedef long long ll;
int n,q,bel[N],r[N],cnt;
ll a[N],add[M],b[M],bj[M];
void gai(int l,int rr,int be,ll x){
    b[be]=-inf;
    for(int i=r[be-1]+1;i<=r[be];i++){
        if(bj[be]!=-inf&&(i<l||i>rr)) a[i]=bj[be];
        else if(i>=l&&i<=rr) a[i]=x;
        b[be]=max(b[be],a[i]);  
    }
    bj[be]=-inf;
    add[be]=0;
    return;
}
void jia(int l,int rr,int be,ll x){
    for(int i=r[be-1]+1;i<=r[be];i++){
        if(bj[be]!=-inf&&(i<l||i>rr)) a[i]=bj[be];
        else if(bj[be]!=-inf&&i>=l&&i<=rr) a[i]=bj[be]+x;
        else if(i>=l&&i<=rr) a[i]+=x;
        b[be]=max(b[be],a[i]+add[be]);  
    }
    bj[be]=-inf;
    return;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    int kk=sqrt(n),now=0;
    while(now<n){
        cnt++;
        now=min(n,now+kk);
        r[cnt]=now;
    }
    now=1;
    b[now]=-inf;
    add[now]=0;
    bj[now]=-inf;
    for(int i=1;i<=n;i++){
        if(i>r[now]){
            now+=1;
            b[now]=-inf;
            add[now]=0;
            bj[now]=-inf;
        }
        bel[i]=now;
        b[now]=max(a[i],b[now]);
    }
    int op,l,rr;
    ll k;
    while(q--){
        scanf("%d%d%d",&op,&l,&rr);
        int bl=bel[l],br=bel[rr];
        if(op==3){
            ll ans=-inf;
            if(bl==br){
                for(int i=l;i<=rr;i++) ans=max(ans,a[i]+add[bl]);
                printf("%lld\n",ans);
                continue;
            }
            for(int i=bl+1;i<=br-1;i++) ans=max(ans,b[i]);
            if(bj[bl]!=-inf) ans=max(ans,bj[bl]+add[bl]);
            else for(int i=l;i<=r[bl];i++) ans=max(ans,a[i]+add[bl]);
            if(bj[br]!=-inf) ans=max(ans,bj[br]+add[br]);
            else for(int i=r[br-1]+1;i<=rr;i++) ans=max(ans,a[i]+add[br]);
            printf("%lld\n",ans);
        }else{
            scanf("%lld",&k);
            if(op==1){
                if(bl==br){
                    gai(l,rr,bl,k);
                    continue;
                }
                gai(l,r[bl],bl,k);
                gai(r[br-1]+1,rr,br,k);
                for(int i=bl+1;i<=br-1;i++){
                    bj[i]=k;
                    b[i]=bj[i];
                    add[i]=0;
                }
            }else{
                if(bl==br){
                    jia(l,rr,bl,k);
                    continue;
                }
                jia(l,r[bl],bl,k);
                jia(r[br-1]+1,rr,br,k);
                for(int i=bl+1;i<=br-1;i++){
                    add[i]+=k;
                    b[i]+=k;
                }
            }
        }
    }
    return 0;
}