分块求调，50pts

4WA，1TLE

#include<bits/stdc++.h>
#define N 2000009
#define M 2009
#define inf 1e15+9
using namespace std;
typedef long long ll;
ll n,m,L,a[N],b[N],bm[M],c[M],v1[M],v2[N];
inline void add(ll l,ll r,ll x){
    if(b[l]==b[r])
        for(int i=l;i<=r;i++){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
    else{
        for(int i=l;b[i]==b[l];i++){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
        for(int i=r;b[i]==b[r];i--){
            if(v1[b[i]]>v2[i]) a[i]=x,v2[i]=v1[b[i]];
            else a[i]+=x;
            bm[b[i]]=max(bm[b[i]],a[i]+c[b[i]]);
        }
        for(int k=b[l]+1;k<=b[r]-1;k++) c[k]+=x,bm[k]+=x;
    }
    return;
}
inline void modi(ll l,ll r,ll x){
    if(b[l]==b[r])
        for(int i=l;i<=r;i++)
            v2[i]=v1[b[i]],a[i]=x;
    else{
        for(int i=l;b[i]==b[l];i++)
            v2[i]=v1[b[i]],a[i]=x;
        for(int i=r;b[i]==b[r];i--)
            v2[i]=v1[b[i]],a[i]=x;
        for(int k=b[l]+1;k<=b[r]-1;k++){
            v1[k]++;
            c[k]=x,bm[k]=x;
        }
    }
    return;
}
inline ll qw(ll l,ll r){
    ll ans=-inf;
    if(b[l]==b[r])
        for(ll i=l;i<=r;i++){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
    else{
        for(ll i=l;b[i]==b[l];i++){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
        for(ll i=r;b[i]==b[r];i--){
            if(v1[b[i]]>v2[i]) ans=max(ans,c[b[i]]);
            else ans=max(ans,a[i]+c[b[i]]);
        }
        for(ll k=b[l]+1;k<=b[r]-1;k++) ans=max(ans,bm[k]);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i];
    L=sqrt(n);
    for(ll i=1;i<=n;i++) b[i]=(i-1)/L+1;
    for(ll k=1;k<=b[n];k++){
        ll r=k*L;
        ll l=r-L+1;
        bm[k]=*max_element(a+l,a+r+1);
    }
    for(ll i=1;i<=m;i++){
        ll l,r,x,op;
        cin>>op>>l>>r;
        if(op==3) cout<<qw(l,r)<<endl;
        else{
            cin>>x;
            if(op==1) modi(l,r,x);
            else add(l,r,x);
        }
    }
    return 0;
}