线段树60pts求调

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e6 + 5, INF = 0x3f3f3f3f;
long long n, q, op, l, r, x, a[maxn];

struct Node{
    long long l, r, maxx, lazy_add, lazy_erase;
    bool flag_add, flag_erase;
}tr[12 * maxn];

void pushup(int k){
    tr[k].maxx = max(tr[k << 1].maxx, tr[k << 1 | 1].maxx);
}

void pushdown(int k){
    int lc = k << 1, rc = k << 1 | 1;
    if(tr[k].flag_erase){
        tr[rc].maxx = tr[lc].maxx = tr[lc].lazy_erase = tr[rc].lazy_erase = tr[k].lazy_erase;
        tr[lc].flag_erase = tr[rc].flag_erase = tr[k].flag_erase;
        tr[k].lazy_erase = 0;
        tr[k].flag_erase = false;
    }

    if(tr[k].flag_add){
        tr[lc].maxx = tr[lc].maxx + tr[k].lazy_add;
        tr[lc].lazy_add += tr[k].lazy_add;

        tr[rc].maxx = tr[rc].maxx + tr[k].lazy_add;
        tr[rc].lazy_add += tr[k].lazy_add;

        tr[lc].flag_add = tr[rc].flag_add = tr[k].flag_add;

        tr[k].lazy_add = 0;
        tr[k].flag_add = false;
    }
}

void lazy_add(int k, int v){
    if(tr[k].flag_erase){
        tr[k].lazy_erase += v;
        tr[k].maxx += v;
    }
    else{
        tr[k].flag_add = true;
        tr[k].lazy_add += v;
        tr[k].maxx += v;
    }
}

void lazy_erase(int k, int v){
    tr[k].flag_erase = true;
    tr[k].lazy_add = 0; 
    tr[k].lazy_erase = v;
    tr[k].maxx = v;
}

void build(int k, int l, int r){
    tr[k].l = l;
    tr[k].r = r;
    tr[k].lazy_add = tr[k].lazy_erase = 0;
    tr[k].flag_add = tr[k].flag_erase = false;
    tr[k].maxx = LONG_LONG_MAX;

    if(l == r){
        tr[k].maxx = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    int lc = k << 1, rc = k << 1 | 1;

    build(lc, l, mid);
    build(rc, mid + 1, r);

    pushup(k);
}

void update_add(int k, int l, int r, int v){
    if(tr[k].l >= l && tr[k].r <= r){
//      pushup(k);
        lazy_add(k, v);
        return;
    }

    if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);

    int mid = (tr[k].l + tr[k].r) >> 1;
    int lc = k << 1, rc = k << 1 | 1;

    if(r <= mid) update_add(lc, l, r, v);
    else if(l > mid) update_add(rc, l, r, v);
    else{
        update_add(lc, l, mid, v);
        update_add(rc, mid + 1, r, v);
    } 

    pushup(k);
}

void update_erase(int k, int l, int r, int v){
    if(tr[k].l >= l && tr[k].r <= r){
//      pushup(k);
        lazy_erase(k, v);
        return;
    }

    if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);

    int mid = (tr[k].l + tr[k].r) >> 1;
    int lc = k << 1, rc = k << 1 | 1;

    if(r <= mid) update_erase(lc, l, r, v);
    else if(l > mid) update_erase(rc, l, r, v);
    else{
        update_erase(lc, l, mid, v);
        update_erase(rc, mid + 1, r, v);
    }

    pushup(k);
}

long long query(int k, int l, int r){
    if(tr[k].l >= l && tr[k].r <= r){
        return tr[k].maxx;
    }

    if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);

    int mid = (tr[k].l + tr[k].r) >> 1;
    int lc = k << 1, rc = k << 1 | 1;
    long long ans = -INF;

    if(r <= mid) ans = query(lc, l, r);
    else if(l > mid) ans = query(rc, l, r);
    else ans = max(query(lc, l, mid), query(rc, mid + 1, r));

    pushup(k);

    return ans; 
}

void print(int k){
    if(tr[k].l){
        print(k << 1);
        cout << k << " l:"<< tr[k].l << " r:" << tr[k].r << " maxx:" << tr[k].maxx 
             << " lazy_add:" << tr[k].lazy_add << " lazy_erase:" << tr[k].lazy_erase << endl;
        print(k << 1 | 1);
    }
}

#define int int

int main(){
    ios::sync_with_stdio(false);
    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 --){
        cin >> op >> l >> r;

        if(op == 1){
            cin >> x;
            update_erase(1, l, r, x);
//          print(1);
        }
        else if(op == 2){
            cin >> x;
            update_add(1, l, r, x);
//          print(1);
        }
        else{
            cout << query(1, l, r) << endl;
//          print(1);
        }
    }

    return 0;
}