$Picks \; loves \; segment \; tree \; VIII$

存档。

查询区间和不知道写的对不对。

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int inf = 2e9;
const int N = 500010;

struct Tag {
    int add, mx, mn;
    void clear() {
        add = mx = mn = 0;
    }
};

Tag operator+ (Tag a, Tag b) {
    a.mx = max(a.mx, a.add + b.mx);
    a.mn = min(a.mn, a.add + b.mn);  
    a.add += b.add;
    return a;
}

struct Max {
    int val, se, his, cnt;
} tmpmx;

Max operator+ (Max a, Max b) {
    if (a.val == b.val) {
        a.se = max(a.se, b.se);
        a.cnt = a.cnt + b.cnt;
    } else if (a.val < b.val) {        
        a.cnt = b.cnt;
        a.se = max(a.val, b.se);
    } else {
        a.se = max(a.se, b.val);
    }   
    a.val = max(a.val, b.val);
    a.his = max(a.his, b.his);
    return a;
}

struct Min {
    int val, se, his, cnt;
} tmpmn;

Min operator+ (Min a, Min b) {
    if (a.val == b.val) {
        a.se = min(a.se, b.se);
        a.cnt = a.cnt + b.cnt;
    } else if (a.val > b.val) {
        a.se = min(a.val, b.se);    
        a.cnt = b.cnt;
    } else {
        a.se = min(a.se, b.val);
    } 
    a.val = min(a.val, b.val);    
    a.his = min(a.his, b.his);
    return a;
}

struct Node {
    int l, r;
    i64 sum;
    Max mx;
    Min mn;
    Tag tmx, tmn, oth;
    void cleartag() {
        tmx.clear();
        tmn.clear();
        oth.clear();
    }
} tr[N << 2];
int n, m;
int w[N];

#define ls (u << 1)
#define rs (u << 1 | 1)

void pushup(int u) {
    tr[u].mx = tr[ls].mx + tr[rs].mx;
    tr[u].mn = tr[ls].mn + tr[rs].mn;
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].sum = w[l];
        tr[u].mn = {w[l], inf, w[l], 1};
        tr[u].mx = {w[l], -inf, w[l], 1};
        return;
    } 
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void pushmn(Node& u, Tag t) {    
    u.sum += 1ll * t.add * u.mn.cnt;
    u.mn.his = min(u.mn.his, u.mn.val + t.mn);
    if (tmpmn.val == tmpmx.se) u.mx.se += t.add;
    u.mn.val += t.add;
    u.tmn = u.tmn + t;
}

void pushmx(Node& u, Tag t) {
    if (tmpmn.val != tmpmx.val) u.sum += 1ll * t.add * u.mx.cnt;
    u.mx.his = max(u.mx.his, u.mx.val + t.mx);
    if (tmpmn.se == tmpmx.val) u.mn.se += t.add;
    u.mx.val += t.add;
    u.tmx = u.tmx + t;
}

void pushoth(Node& u, Tag t) {
    int cnt = u.r - u.l + 1;
    if (tmpmn.val == tmpmx.val) cnt -= u.mx.cnt;
    else cnt -= u.mx.cnt + u.mn.cnt;
    u.sum += 1ll * t.add * cnt;
    if (tmpmn.se != tmpmx.val && u.mn.se != inf) u.mn.se += t.add;
    if (tmpmx.se != tmpmn.val && u.mx.se != -inf) u.mx.se += t.add;
    u.oth = u.oth + t;
}

void pushall(Node& u, Tag t) {
    u.sum += 1ll * t.add * (u.r - u.l + 1);
    if (u.mx.se != -inf) u.mx.se += t.add;
    if (u.mn.se != inf) u.mn.se += t.add;
    u.mx.his = max(u.mx.his, u.mx.val += t.add);
    u.mn.his = min(u.mn.his, u.mn.val += t.add);
    u.tmn = u.tmn + t;
    u.tmx = u.tmx + t;
    u.oth = u.oth + t;
}

void pushdown(int x) {
    Node &u = tr[x], &l = tr[x << 1], &r = tr[x << 1 | 1];

    int mn = min(l.mn.val, r.mn.val);
    int mx = max(l.mx.val, r.mx.val);

    tmpmn = l.mn, tmpmx = l.mx;
    if (l.mn.val == mn) pushmn(l, u.tmn);
    else if (l.mn.val == mx) pushmn(l, u.tmx);
    else pushmn(l, u.oth);
    if (l.mx.val == mx) pushmx(l, u.tmx);
    else if (l.mx.val == mn) pushmx(l, u.tmn);
    else pushmx(l, u.oth);  
    pushoth(l, u.oth);

    tmpmn = r.mn, tmpmx = r.mx;
    if (r.mn.val == mn) pushmn(r, u.tmn);
    else if (r.mn.val == mx) pushmn(r, u.tmx);
    else pushmn(r, u.oth);
    if (r.mx.val == mx) pushmx(r, u.tmx);
    else if (r.mx.val == mn) pushmx(r, u.tmn);
    else pushmx(r, u.oth);  
    pushoth(r, u.oth);

    u.cleartag();
}

void cmax(int u, int l, int r, int v) {  
    if (tr[u].mn.val >= v) return;
    if (tr[u].l >= l && tr[u].r <= r && tr[u].mn.se > v) {
        v -= tr[u].mn.val;   
        tmpmx = tr[u].mx, tmpmn = tr[u].mn;
        if (tr[u].mx.val == tr[u].mn.val) pushmx(tr[u], {v, v, v});
        return pushmn(tr[u], {v, v, v});
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cmax(u << 1, l, r, v);
    if (r > mid) cmax(u << 1 | 1, l, r, v);
    pushup(u);
}

void cmin(int u, int l, int r, int v) {    
    if (tr[u].mx.val <= v) return; 
    if (tr[u].l >= l && tr[u].r <= r && tr[u].mx.se < v) {
        v -= tr[u].mx.val;    
        tmpmx = tr[u].mx, tmpmn = tr[u].mn;
        if (tr[u].mx.val == tr[u].mn.val) pushmn(tr[u], {v, v, v});
        return pushmx(tr[u], {v, v, v});
    }  
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1; 
    if (l <= mid) cmin(u << 1, l, r, v);
    if (r > mid) cmin(u << 1 | 1, l, r, v);
    pushup(u);
}

void add(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) 
        return pushall(tr[u], {v, v, v});
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) add(u << 1, l, r, v);
    if (r > mid) add(u << 1 | 1, l, r, v);
    pushup(u);
}

int query_mn(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.val;
    int mid = tr[u].l + tr[u].r >> 1, res = inf;
    pushdown(u);
    if (l <= mid) res = min(res, query_mn(u << 1, l, r));
    if (r > mid) res = min(res, query_mn(u << 1 | 1, l, r));
    return res;
}

int query_hmn(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.his;
    int mid = tr[u].l + tr[u].r >> 1, res = inf;
    pushdown(u);
    if (l <= mid) res = min(res, query_hmn(u << 1, l, r));
    if (r > mid) res = min(res, query_hmn(u << 1 | 1, l, r));
    return res;
}

int query_hmx(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx.his;
    int mid = tr[u].l + tr[u].r >> 1, res = -inf;
    pushdown(u);
    if (l <= mid) res = max(res, query_hmx(u << 1, l, r));
    if (r > mid) res = max(res, query_hmx(u << 1 | 1, l, r));
    return res;
}

i64 query_sum(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    i64 res = 0;
    pushdown(u);
    if (l <= mid) res += query_sum(u << 1, l, r);
    if (r > mid) res += query_sum(u << 1 | 1, l, r);
    return res;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    build(1, 1, n);
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            add(1, l, r, x);
        }
        if (op == 2) {
            cin >> x;
            cmax(1, l, r, x);
        }
        if (op == 3) {
            cout << query_mn(1, l, r) << '\n';
        }
        if (op == 4) {
            cout << query_hmn(1, l, r) << '\n';
        }
        if (op == 5) {
            cin >> x;
            cmin(1, l, r, x);
        }
        if (op == 6) {
            cout << query_hmx(1, l, r) << '\n';
        }
        if (op == 7) {
            cout << query_sum(1, l, r) << '\n';
        }
    }
    return 0;
}