WA #7 #8 #9 #10

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5,inf=0x3f3f3f3f3f3f3f3f;
int n,m;
int tr[N<<2],tag[N<<2],upd[N<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p){tr[p]=max(tr[ls(p)],tr[rs(p)]);}
void addtag(int p,int pl,int pr,int d)
{
    tr[p]+=d;
    tag[p]+=d;
}
void addupd(int p,int pl,int pr,int d)
{
    tr[p]=d;
    upd[p]=d;
}
void pushdown(int p,int pl,int pr)
{
    int mid=pl+pr>>1;

    if(upd[p]!=inf)
    {
        addupd(ls(p),pl,mid,upd[p]);
        addupd(rs(p),mid+1,pr,upd[p]);
        upd[p]=inf;
    }
    if(tag[p])
    {
        addtag(ls(p),pl,mid,tag[p]);
        addtag(rs(p),mid+1,pr,tag[p]);
        tag[p]=0;
    }
  
    
    
}
void build(int p,int pl,int pr)
{
    upd[p]=inf;tag[p]=0;
    if(pl==pr)
    {
        cin>>tr[p];
        return ;
    }
    int mid=pl+pr>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    pushup(p);
}
void add(int p,int pl,int pr,int L,int R,int d)
{
    if(R<pl||pr<L)
        return ;
    if(L<=pl&&pr<=R)
    {
        addtag(p,pl,pr,d);
        return ;
    }
    int mid=pl+pr>>1;
    pushdown(p,pl,pr);
    add(ls(p),pl,mid,L,R,d);
    add(rs(p),mid+1,pr,L,R,d);
    pushup(p);
}
void update(int p,int pl,int pr,int L,int R,int d)
{
    if(R<pl||pr<L)
        return ;
    if(L<=pl&&pr<=R)
    {
        addupd(p,pl,pr,d);
        return ;
    }
    int mid=pl+pr>>1;
    pushdown(p,pl,pr);
    update(ls(p),pl,mid,L,R,d);
    update(rs(p),mid+1,pr,L,R,d);
    pushup(p);
}
int query(int p,int pl,int pr,int L,int R)
{
    if(R<pl||pr<L)
        return -inf;
    if(L<=pl&&pr<=R)
        return tr[p];
    int mid=pl+pr>>1;
    pushdown(p,pl,pr);
    return max(query(ls(p),pl,mid,L,R),query(rs(p),mid+1,pr,L,R));
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--)
    {
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==1)
        {
            cin>>x;
            update(1,1,n,l,r,x);
        }
        if(op==2)
        {
            cin>>x;
            add(1,1,n,l,r,x);
        }
        
        if(op==3)
            cout<<query(1,1,n,l,r)<<'\n';
    }

}