萌新菜鸡刚学OI，分块裸题20分求调

// Problem:P1253
// From:B (A.CDT,B.LG,C.CF,D.ZCX,E.AT)
// URL:https://www.luogu.com.cn/problem/P1253
// Author:C (A.dcj666,B.杜承俊,C.duchengjun)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
namespace get_out{
    char B[1<<20],*S=B,*T=B;char op;
    inline void read_(int &x){x=0;int fi(1);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1;while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();x*=fi;return;}
    inline void read_(long long &x){x=0;int fi(1);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1;while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();x*=fi;return;}
    inline void read_(double &x){x=0.0;float fi(1.0),sm(0.0);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1.0;while(op>='0'&&op<='9') x=(x*10.0)+(op^48),op=getchar();if(op=='.') op=getchar();int rtim=0;while(op>='0'&&op<='9') sm=(sm*10.0)+(op^48),++rtim,op=getchar();while(rtim--) sm/=10.0;x+=sm,x*=fi;return;}
    inline void read_(string &s){char c(getchar());s="";while(!isgraph(c)&&c!=EOF) c=getchar();for(;isgraph(c);c=getchar()) s+=c;}
    inline void read_(char &c){for(c=op;c==' '||c=='\n'||c=='\r'||c=='\t';c=getchar());op=c;}
    template<typename Head,typename ...Tail>
    inline void read_(Head& h,Tail&... t){read_(h),read_(t...);}
    inline void write_(){}
    inline void postive_write(unsigned x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(unsigned long long x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(int x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(long long x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(short x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void write_(const char* ss) {while(*ss) putchar(*ss++);}
    inline void write_(char c) {putchar(c);}
    inline void write_(string s) {for(unsigned i=0;i<s.size();++i) putchar(s[i]);}
    inline void write_(short x){if(x<0) putchar('-'),postive_write(-x);else postive_write(x);}
    inline void write_(int x){if(x<0) x=-x,putchar('-');postive_write(x);}
    inline void write_(long long x){if(x<0) x=-x,putchar('-');postive_write(x);}
    inline void write_(unsigned x) {postive_write(x);}
    inline void write_(ull x) {postive_write(x);}
    template<typename Head,typename ...Tail>
    inline void write_(Head h,Tail ...t) {write_(h),write_(t...);}
}
using get_out::read_;using get_out::write_;
const int N=1e6+10;
const ll INF=0x7FFFFFFFFFFFFFFF;
struct block{
    int n,m;
    int L[N],R[N],pos[N];
    ll a[N],mx[N],add[N],change[N];
    int opt,l,r;ll x;
    void CIN(){
        read_(n,m);
        for(int i=1;i<=n;i++)read_(a[i]);
    }
    void build(){
        int t=sqrt(n*1.0);
        int num=n/t;
        if(n%t)num++;
        for(int i=1;i<=num;i++)
            L[i]=(i-1)*t+1,R[i]=i*t;
        R[num]=n;
        for(int i=1;i<=num;i++){
            mx[i]=change[i]=-INF;
            add[i]=0;
            for(int j=L[i];j<=R[i];j++)
                pos[j]=i,mx[i]=max(mx[i],a[j]);
        }
    }
    void update1_small(int l,int r,int p,ll x){
        mx[p]=x;
        for(int i=L[p];i<=R[p];i++){
            if(i>=l&&i<=r)a[i]=x;
            else
                if(change[p]!=-INF)a[i]=change[p]+add[p];
                else a[i]+=add[p];
            mx[p]=max(mx[p],a[i]);
        }
        add[p]=0,change[p]=-INF;
//      for(int i=1;i<=n;i++)
//          write_(a[i]," ");
//      write_("\n");
    }
    void update1(int l,int r,ll x){
        int p=pos[l],q=pos[r];
        if(p==q)update1_small(l,r,p,x);
        else{
            for(int i=p+1;i<=q-1;i++)mx[i]=change[i]=x,add[i]=0;
            update1_small(l,R[p],p,x),update1_small(L[q],r,q,x);
        }
    }
    void update2_small(int l,int r,int p,ll x){
        mx[p]=-INF;
        for(int i=L[p];i<=R[p];i++){
            if(change[p]!=-INF)a[i]=change[p];
            a[i]+=add[p];
            if(i>=l&&i<=r)a[i]+=x;
            mx[p]=max(mx[p],a[i]);
        }
        add[p]=0,change[p]=-INF;
    }
    void update2(int l,int r,ll x){
        int p=pos[l],q=pos[r];
//      write_(l," ",r," ",x,"\n");
        if(p==q)update2_small(l,r,p,x);
        else{
            for(int i=p+1;i<=q-1;i++)if(change[i]==INF)add[i]+=x,mx[i]+=add[i];else add[i]+=x,mx[i]=change[i]+add[i];
            update2_small(l,R[p],p,x),update2_small(L[q],r,q,x);
        }
    }
    ll query_small(int l,int r,int p){
        if(change[p]!=-INF)return change[p]+add[p];
        ll ans=-INF;
        for(int i=l;i<=r;i++)ans=max(ans,a[i]+add[p]);
        return ans;
    }
    ll query(int l,int r){
        int p=pos[l],q=pos[r];
        ll ans=-INF;
        if(p==q)ans=query_small(l,r,p);
        else{
            for(int i=p+1;i<=q-1;i++)
                if(change[i]!=-INF)ans=max(ans,change[i]+add[i]);
                else ans=max(ans,mx[i]+add[i]);
            ans=max(ans,max(query_small(l,R[p],p),query_small(L[q],r,q)));
        }
        return ans;
    }
    void COUT(){
        while(m--){
            read_(opt,l,r);
            if(opt==1){
                read_(x);
                update1(l,r,x);
            }else if(opt==2){
                read_(x);
                update2(l,r,x);
            }else if(opt==3)
                write_(query(l,r),"\n");
//          for(int i=1;i<=n;i++)
//              if(change[pos[i]]!=-INF)write_(change[pos[i]]+add[pos[i]]," ");
//              else write_(a[i]+add[pos[i]]," ");
//          write_('\n');
        }
    }
}a;
signed main(void){
    std::ios::sync_with_stdio(false);
    a.CIN();
    a.build();
    a.COUT();
    return 0;
}