题解：P11318 [RMI 2021] 奇树 / Weirdtree

· · 题解

午睡醒来检验清醒程度。

考虑这个修改在干什么：把最大值一层一层往下推平，直到某一层 k 不够用了，最后这一层只能减一部分。

这其实就是 Segment tree beats 干的事情，具体地说，记录管辖区间内最大值 \text{max}、次大值 \text{secmax}、最大值个数 \text{cnt}，最大值被推到的标记 \text{tag}，以及此时的总和 \text{sum}。

对于前面完整的若干层，会将最大值削减至 \max(\text{secmax},\text{max}-\lfloor k/\text{cnt}\rfloor)，进到子树里面修改即可，写法和模板题是完全一样的。

对于最后不完整的一层，只有一段前缀内的最大值会被修改，写一个类似线段树二分的东西即可。

单点修改直接改即可。根据单点修改的 Beats 的势能分析，时间复杂度为 \mathcal O((n+q)\log n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n;
struct node { int mx, mx2, ct, tg; ll sm; } t[N << 2];
#define lc (p << 1)
#define rc (lc | 1)
inline node operator+(const node &a, const node &b) {
    node c;
    if (a.mx == b.mx)
        c.mx = a.mx, c.mx2 = max(a.mx2, b.mx2), c.ct = a.ct + b.ct;
    else if (a.mx > b.mx)
        c.mx = a.mx, c.mx2 = max(a.mx2, b.mx), c.ct = a.ct;
    else
        c.mx = b.mx, c.mx2 = max(a.mx, b.mx2), c.ct = b.ct;
    c.tg = -1, c.sm = a.sm + b.sm;
    return c;
}
void build(int p, int l, int r, int a[]) {
    if (l == r) return void(t[p] = {a[l], -1, 1, -1, a[l]});
    int mid = (l + r) >> 1;
    build(lc, l, mid, a), build(rc, mid + 1, r, a);
    t[p] = t[lc] + t[rc];
}
inline void assign(int p, int v) {
    if (t[p].mx > v) t[p].sm -= ll(t[p].mx - v) * t[p].ct, t[p].mx = t[p].tg = v;
}
inline void pushdown(int p) {
    if (~t[p].tg) assign(lc, t[p].tg), assign(rc, t[p].tg), t[p].tg = -1;
}
void update(int p, int l, int r, int L, int R, int v) {
    if (t[p].mx <= v) return;
    if (L <= l && r <= R) {
        if (l == r || t[p].mx2 < v) return assign(p, v);
    }
    pushdown(p);
    int mid = (l + r) >> 1;
    if (L <= mid) update(lc, l, mid, L, R, v);
    if (R > mid) update(rc, mid + 1, r, L, R, v);
    t[p] = t[lc] + t[rc];
}
void modify(int p, int l, int r, int x, int v) {
    if (l == r) return void(t[p] = {v, -1, 1, -1, v});
    pushdown(p);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lc, l, mid, x, v);
    else modify(rc, mid + 1, r, x, v);
    t[p] = t[lc] + t[rc];
}
node query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[p];
    pushdown(p);
    int mid = (l + r) >> 1;
    if (R <= mid) return query(lc, l, mid, L, R);
    if (L > mid) return query(rc, mid + 1, r, L, R);
    return query(lc, l, mid, L, R) + query(rc, mid + 1, r, L, R);
}
void consume(int p, int l, int r, int L, int R, int v, int &rem) {
    if (!rem || t[p].mx < v) return;
    if (L <= l && r <= R) {
        if (l == r || t[p].mx2 < v - 1 && rem >= t[p].ct)
            return rem -= t[p].ct, assign(p, v - 1);
    }
    pushdown(p);
    int mid = (l + r) >> 1;
    if (L <= mid) consume(lc, l, mid, L, R, v, rem);
    if (R > mid) consume(rc, mid + 1, r, L, R, v, rem);
    t[p] = t[lc] + t[rc];
}
void initialise(int N, int Q, int h[]) {
    build(1, 1, n = N, h);
}
void cut(int l, int r, int k) {
    while (k) {
        node p = query(1, 1, n, l, r);
        if (!p.mx) return;
        if (k < p.ct) return consume(1, 1, n, l, r, p.mx, k);
        int v = max(0, max(p.mx2, p.mx - k / p.ct));
        k -= (p.mx - v) * p.ct, update(1, 1, n, l, r, v);
    }
}
void magic(int i, int x) { modify(1, 1, n, i, x); }
long long int inspect(int l, int r) { return query(1, 1, n, l, r).sm; }
/*
庭中有奇树，绿叶发华滋。
攀条折其荣，将以遗所思。
馨香盈怀袖，路远莫致之。
此物何足贵？但感别经时。
*/
#ifdef WorldMachine
int h[N];
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, Q; cin >> N >> Q;
    for (int i = 1; i <= N; i++) cin >> h[i];
    initialise(N, Q, h);
    while (Q--) {
        int op; cin >> op;
        if (op == 1) {
            int l, r, k; cin >> l >> r >> k;
            cut(l, r, k);
        } else if (op == 2) {
            int i, x; cin >> i >> x;
            magic(i, x);
        } else {
            int l, r; cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
}
#endif