线段树求调

RT

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+100;
struct node{
    LL l,r;
    LL maxn,add,num;
}tr[N<<2];
int a[N];
int n,q;
void pushup(int u){
    tr[u].maxn = max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}
void coverpushdown(int u){
    if(tr[u].num != 0x3f3f3f3f){
        tr[u<<1].add = tr[u<<1|1].add = 0;
        tr[u<<1].maxn = tr[u<<1|1].maxn = tr[u].maxn;
        tr[u<<1].num = tr[u<<1|1].num = tr[u].num;
        tr[u].num = 0x3f3f3f3f;
    }
}
void addpushdown(int u){
    if(tr[u].add){
        coverpushdown(u);
        tr[u<<1|1].maxn += tr[u].add;
        tr[u<<1|1].maxn += tr[u].add;
        tr[u<<1].add += tr[u].add;
        tr[u<<1|1].add += tr[u].add;
        tr[u].add = 0;
    }
}
void pushdown(int u){
    coverpushdown(u);
    addpushdown(u);
}
void build(int u,int l,int r){
    if(l == r){
        tr[u] = {l,l,a[l],0,0x3f3f3f3f};
    }else{
        tr[u] = {l,r,0,0,0x3f3f3f3f};
        int mid = l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int add){
    if(tr[u].l >= l && tr[u].r <= r){
        coverpushdown(u);
        tr[u].maxn += add;
        tr[u].add += add;
    }else{
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        if(l <= mid)    modify(u<<1,l,mid,add);
        if(r > mid) modify(u<<1|1,mid+1,r,add);
        pushup(u);
    }
}
void change(int u,int l,int r,int k){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].maxn = k;
        tr[u].add = 0;
        tr[u].num = k;
    }else{
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        if(l <= mid)    modify(u<<1,l,mid,k);
        if(r > mid) modify(u<<1|1,mid+1,r,k);
        pushup(u);
    }
}
LL query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r){
        return tr[u].maxn;
    }else{
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        LL ans = -0x3f3f3f3f;
        if(l <= mid)    ans = max(ans,query(u<<1,l,mid));
        if(r > mid) ans = max(ans,query(u<<1|1,mid+1,r));
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    build(1,1,n);
    while(q--){
        int op,x,y,z;
        cin >> op >> x >> y;
        if(op == 1){
            cin >> z;
            change(1,x,y,z);
        }else if(op == 2){
            cin >> z;
            modify(1,x,y,z);
        }else{
            cout << query(1,x,y) << endl;
        }
    }

    return 0;
}