20pts(悬2关)

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll N = 1e6+5;
const ll INF = -0x3f3f3f3f3f3f3f3;
ll a[N];
struct node{
    ll maxn,l,r,lazy_change,lazy_add;
}tree[N<<2];
void init(ll l,ll r,ll p){
    tree[p].l = l;
    tree[p].r = r;
    tree[p].maxn = INF;
    tree[p].lazy_change = INF;
    if(l == r){
        tree[p].maxn = a[l];
        return;
    }
    ll mid = (l+r)>>1;
    init(l,mid,p<<1);
    init(mid+1,r,p<<1|1);
    tree[p].maxn = max(tree[p<<1].maxn,tree[p<<1|1].maxn);
    return;
}
void pushdown_add(ll p){
    if(tree[p].lazy_add){
        tree[p].maxn += tree[p].lazy_add;
        tree[p<<1].lazy_add += tree[p].lazy_add;
        tree[p<<1|1].lazy_add += tree[p].lazy_add;
        tree[p].lazy_add = 0;
    }
}
void pushdown_change(ll p){
    if(tree[p].lazy_change != INF){
        tree[p<<1].lazy_add = 0;
        tree[p<<1|1].lazy_add = 0;

        tree[p<<1].maxn = tree[p].lazy_change;
        tree[p<<1|1].maxn = tree[p].lazy_change;

        tree[p<<1].lazy_change = tree[p].lazy_change;
        tree[p<<1|1].lazy_change = tree[p].lazy_change;

        tree[p].lazy_change = INF;
    }
}
void add(ll l,ll r,ll c,ll p){
    if(tree[p].l == l && tree[p].r == r){
        pushdown_change(p);
        tree[p].lazy_add += c;
        tree[p].maxn += c;
        return;
    }
    pushdown_change(p);
    pushdown_add(p);
    if(tree[p<<1].r >= r){
        add(l,r,c,p<<1);
    }else if(tree[p<<1|1].l <= l){
        add(l,r,c,p<<1|1);
    }else{
        add(l,tree[p<<1].r,c,p<<1);
        add(tree[p<<1|1].l,r,c,p<<1|1);
    }
    tree[p].maxn = max(tree[p<<1].maxn,tree[p<<1|1].maxn);
}
void change(ll l,ll r,ll c,ll p){
    if(tree[p].l == l && tree[p].r == r){
        tree[p].lazy_add = 0;
        tree[p].lazy_change = c;
        tree[p].maxn = c;
        return;
    }
    pushdown_change(p);
    pushdown_add(p);
    if(tree[p<<1].r >= r){
        change(l,r,c,p<<1);
    }else if(tree[p<<1|1].l <= l){
        change(l,r,c,p<<1|1);
    }else{
        change(l,tree[p<<1].r,c,p<<1);
        change(tree[p<<1|1].l,r,c,p<<1|1);
    }
    tree[p].maxn = max(tree[p<<1].maxn,tree[p<<1|1].maxn);
}
ll query(ll l,ll r,ll p){
    if(tree[p].l == l && tree[p].r == r){
        return tree[p].maxn;
    }
    pushdown_change(p);
    pushdown_add(p);
    if(tree[p<<1].r >= r){
        return query(l,r,p<<1);
    }else if(tree[p<<1|1].l <= l){
        return query(l,r,p<<1|1);
    }else{
        return max(query(l,tree[p<<1].r,p<<1),query(tree[p<<1|1].l,r,p<<1|1));
    }
}
int main(){
    ll n,q,opt,l,r,x;
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    init(1,n,1);
    for(ll i=1;i<=q;i++){
        scanf("%lld",&opt);
        if(opt == 1){
            scanf("%lld%lld%lld",&l,&r,&x);
            change(l,r,x,1);
        }else if(opt == 2){
            scanf("%lld%lld%lld",&l,&r,&x);
            add(l,r,x,1);
        }else if(opt == 3){
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(l,r,1));
        }
    }
}