20pts求调

#pragma G++ optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
    template<typename type>
    inline void read(type &ret){
        ret=0;int w(1);char c(getchar());
        while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
        while(c>='0'&&c<='9'){ret=ret*10+(c^48);c=getchar();}
        ret=ret*w;
    }
    template<typename type>
    inline void write(type x){
        short st[50],top(0);
        if(x<0){putchar('-');x=-x;}
        do{st[++top]=x%10;x/=10;}while(x);
        while(top)putchar(st[top--]+48);
    }
}
const int N=1e6+5;
const ll inf=1e18;
int n,q;
ll a[N];
struct node{
    ll mx,tag1,tag2;
}tr[N<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
inline void pushup(int p){tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);}
void build(int p,int pl,int pr){
    tr[p].mx=tr[p].tag1=tr[p].tag2=-inf;
    if(pl==pr){
        tr[p].mx=a[pl];
        return ;
    }int mid=pl+(pr-pl>>1);
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    pushup(p);
}
inline void addtag1(int p,ll k){
    if(tr[p].tag1==-inf)tr[p].tag1=k;
    else tr[p].tag1+=k;
    tr[p].tag2=-inf;
    tr[p].mx=k;
}
inline void addtag2(int p,ll k){
    if(tr[p].tag1!=-inf){
        tr[p].tag1+=k;
        tr[p].mx+=k;
    }else{
        if(tr[p].tag2==-inf)tr[p].tag2=k;
        else tr[p].tag2+=k;
        tr[p].mx+=k;
    }
}
inline void pushdown(int p){
    if(tr[p].tag1!=-inf||tr[p].tag2!=-inf){
        if(tr[p].tag1!=inf){
            addtag1(ls(p),tr[p].tag1);
            addtag1(rs(p),tr[p].tag1);
            tr[p].tag1=-inf;
        }else if(tr[p].tag2!=inf){
            addtag2(ls(p),tr[p].tag2);
            addtag2(rs(p),tr[p].tag2);
            tr[p].tag2=-inf;
        }
    }
}
void modify1(int p,int pl,int pr,int L,int R,ll k){
    if(L<=pl&&pr<=R){
        addtag1(p,k);
        return ;
    }pushdown(p);
    int mid=pl+(pr-pl>>1);
    if(L<=mid)modify1(ls(p),pl,mid,L,R,k);
    if(mid<R)modify1(rs(p),mid+1,pr,L,R,k);
    pushup(p);
}
// add
void modify2(int p,int pl,int pr,int L,int R,ll k){
    if(L<=pl&&pr<=R){
        addtag2(p,k);
        return ;
    }pushdown(p);
    int mid=pl+(pr-pl>>1);
    if(L<=mid)modify2(ls(p),pl,mid,L,R,k);
    if(mid<R)modify2(rs(p),mid+1,pr,L,R,k);
    pushup(p);
}
// query
ll query(int p,int pl,int pr,int L,int R){
    if(L<=pl&&pr<=R)return tr[p].mx;
    pushdown(p);
    int mid=pl+(pr-pl>>1);ll res=-inf;
    if(L<=mid)res=max(res,query(ls(p),pl,mid,L,R));
    if(mid<R)res=max(res,query(rs(p),mid+1,pr,L,R));
    return res;
}
int main(){
    using namespace IO;
    read(n),read(q);
    for(int i=1;i<=n;++i)read(a[i]);
    build(1,1,n);
    for(int i=1;i<=q;++i){
        int op,l,r;ll x;
        read(op);
        if(op==1){
            read(l),read(r),read(x);
            modify1(1,1,n,l,r,x);
        }else if(op==2){
            read(l),read(r),read(x);
            modify2(1,1,n,l,r,x);
        }else{
            read(l),read(r);
            write(query(1,1,n,l,r)),putchar('\n');
        }
    }
    return 0;
}