python/TangDou/AcWing/SegmentTree/Gorgeous/P6242_2.cpp

#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
const int N = 2000005;
#define ls u << 1
#define rs u << 1 | 1
// 快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int n, m, op, l, r, k, v;
struct Node {
    ll sum;
    int l, r, maxa, cnt, se, maxb;
    int add1, add2, add3, add4;
} tr[N];

inline void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    tr[u].maxa = max(tr[ls].maxa, tr[rs].maxa);
    tr[u].maxb = max(tr[ls].maxb, tr[rs].maxb);
    if (tr[ls].maxa == tr[rs].maxa) {
        tr[u].se = max(tr[ls].se, tr[rs].se);
        tr[u].cnt = tr[ls].cnt + tr[rs].cnt;
    } else if (tr[ls].maxa > tr[rs].maxa) {
        tr[u].se = max(tr[ls].se, tr[rs].maxa);
        tr[u].cnt = tr[ls].cnt;
    } else {
        tr[u].se = max(tr[ls].maxa, tr[rs].se);
        tr[u].cnt = tr[rs].cnt;
    }
}

void build(int l, int r, int u) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].sum = tr[u].maxa = tr[u].maxb = read();
        tr[u].cnt = 1, tr[u].se = -2e9;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, u * 2), build(mid + 1, r, u * 2 + 1);
    pushup(u);
}

inline void change(int k1, int k2, int k3, int k4, int u) {
    tr[u].sum += 1ll * k1 * tr[u].cnt + 1ll * k2 * (tr[u].r - tr[u].l + 1 - tr[u].cnt);
    tr[u].maxb = max(tr[u].maxb, tr[u].maxa + k3);
    tr[u].maxa += k1;
    if (tr[u].se != -2e9) tr[u].se += k2;
    tr[u].add3 = max(tr[u].add3, tr[u].add1 + k3);
    tr[u].add4 = max(tr[u].add4, tr[u].add2 + k4);
    tr[u].add1 += k1, tr[u].add2 += k2;
}

inline void pushdown(int u) {
    int maxn = max(tr[u * 2].maxa, tr[u * 2 + 1].maxa);
    if (tr[u * 2].maxa == maxn)
        change(tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4, u * 2);
    else
        change(tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4, u * 2);
    if (tr[u * 2 + 1].maxa == maxn)
        change(tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4, u * 2 + 1);
    else
        change(tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4, u * 2 + 1);
    tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
}

void update_add(int u) {
    if (l > tr[u].r || r < tr[u].l) return;
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += 1ll * k * tr[u].cnt + 1ll * k * (tr[u].r - tr[u].l + 1 - tr[u].cnt);
        tr[u].maxa += k;
        tr[u].maxb = max(tr[u].maxb, tr[u].maxa);
        if (tr[u].se != -2e9) tr[u].se += k;
        tr[u].add1 += k, tr[u].add2 += k;
        tr[u].add3 = max(tr[u].add3, tr[u].add1);
        tr[u].add4 = max(tr[u].add4, tr[u].add2);
        return;
    }
    pushdown(u);
    update_add(ls), update_add(rs);
    pushup(u);
}

void update_min(int p) {
    if (l > tr[p].r || r < tr[p].l || v >= tr[p].maxa) return;
    if (l <= tr[p].l && tr[p].r <= r && tr[p].se < v) {
        int k = tr[p].maxa - v;
        tr[p].sum -= 1ll * tr[p].cnt * k;
        tr[p].maxa = v, tr[p].add1 -= k;
        return;
    }
    pushdown(p);
    update_min(p * 2), update_min(p * 2 + 1);
    pushup(p);
}

ll query_sum(int p) {
    if (l > tr[p].r || r < tr[p].l) return 0;
    if (l <= tr[p].l && tr[p].r <= r) return tr[p].sum;
    pushdown(p);
    return query_sum(p * 2) + query_sum(p * 2 + 1);
}

int query_maxa(int p) {
    if (l > tr[p].r || r < tr[p].l) return -2e9;
    if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxa;
    pushdown(p);
    return max(query_maxa(p * 2), query_maxa(p * 2 + 1));
}

int query_maxb(int p) {
    if (l > tr[p].r || r < tr[p].l) return -2e9;
    if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxb;
    pushdown(p);
    return max(query_maxb(p * 2), query_maxb(p * 2 + 1));
}

int main() {
    n = read(), m = read();

    build(1, n, 1);

    while (m--) {
        op = read(), l = read(), r = read();
        if (op == 1) k = read(), update_add(1);
        if (op == 2) v = read(), update_min(1);
        if (op == 3) printf("%lld\n", query_sum(1));
        if (op == 4) printf("%d\n", query_maxa(1));
        if (op == 5) printf("%d\n", query_maxb(1));
    }
    return 0;
}