题解：P10639 BZOJ4695 最佳女选手

_IceCream_ · 2024-07-25 10:12:05 · 题解

Content

给你一个长度为 n 的数列 a，需要你实现以下操作：

1. 1 l r x，将 [l, r] 区间内所有数加 x；
2. 2 l r x，\forall l \le i \le r, a_i \leftarrow \max(a_i, x)；
3. 3 l r x，\forall l \le i \le r, a_i \leftarrow \min(a_i, x)；
4. 4 l r，输出 \sum _ {i = l} ^ r a_i。
5. 5 l r，输出 \max _ {i = l} ^ r a_i。
6. 6 l r，输出 \min _ {i = l} ^ r a_i。

Solution

看到 2, 3 操作一眼吉司机线段树板子题。

但是我更喜欢拿这道题当吉司机板子，因为隔壁的 P6242 【模板】线段树 3 多了一个区间历史最值。

先考虑取 min 的情况吧。

我们考虑记录一个严格次大值 se 和区间最大值的个数 cnt，那么取 min 时就会有以下三种情况：

1. 当 mx \le x 时，此时 x 不会对区间造成任何修改，直接退出。
2. 当 se \lt x \lt mx 时，此时只有区间中的最大值会被更新，那么区间和就会加上 cnt \cdot (x - mx)，打上标记就可以推出了。
3. 当 se \ge x 时，此时我们不知道会更新多少个数，那么就直接暴力搜索子树。

这就是吉司机线段树的基本思想，可以势能分析证明它的复杂度是 O(n \log^2 n) 的。

Code

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 5e5 + 5, Inf = 1e18;
int n, m, a[N];

struct Seg {
    int mi, si, ci; // 最小，次小，最小个数
    int mx, sx, cx;
    int lazs, lazx, lazi;
    long long sum;
} tree[N << 2];

//void debug (int node) { printf ("Debug mi %lld si %lld ci %lld mx %lld sx %lld cx %lld lazs %lld lazx %lld lazi %lld sum %lld\n", tree[node].mi, tree[node].si, tree[node].ci, tree[node].mx, tree[node].sx, tree[node].cx, tree[node].lazs, tree[node].lazx, tree[node].lazi, tree[node].sum); }

void pushup (int node) {
    int ls = node << 1, rs = (node << 1) + 1;
    tree[node].sum = tree[ls].sum + tree[rs].sum;
    tree[node].mx = max (tree[ls].mx, tree[rs].mx);
    tree[node].mi = min (tree[ls].mi, tree[rs].mi);

        // 需要根据两棵子树的情况分讨，最小值也是一样的。
    if (tree[ls].mx == tree[rs].mx) {
        tree[node].sx = max (tree[ls].sx, tree[rs].sx);
        tree[node].cx = tree[ls].cx + tree[rs].cx;
    } else if (tree[ls].mx > tree[rs].mx) {
        tree[node].sx = max (tree[ls].sx, tree[rs].mx);
        tree[node].cx = tree[ls].cx;
    } else {
        tree[node].sx = max (tree[ls].mx, tree[rs].sx);
        tree[node].cx = tree[rs].cx;
    }

    if (tree[ls].mi == tree[rs].mi) {
        tree[node].si = min (tree[ls].si, tree[rs].si);
        tree[node].ci = tree[ls].ci + tree[rs].ci;
    } else if (tree[ls].mi < tree[rs].mi) {
        tree[node].si = min (tree[ls].si, tree[rs].mi);
        tree[node].ci = tree[ls].ci;
    } else {
        tree[node].si = min (tree[ls].mi, tree[rs].si);
        tree[node].ci = tree[rs].ci;
    }
}

void pushdown (int node, int l, int r) {
    int ls = node << 1, rs = (node << 1) + 1, mid = l + ((r - l) >> 1);
    int x;

    if (tree[node].lazs) {
        x = tree[node].lazs;
        tree[ls].sum += (mid - l + 1LL) * x; 
        tree[ls].mx += x; tree[ls].mi += x;
        tree[ls].lazs += x;
                // 记得特判
        if (tree[ls].sx != -Inf) tree[ls].sx += x;
        if (tree[ls].si != Inf) tree[ls].si += x;
        if (tree[ls].lazx != -Inf) tree[ls].lazx += x;
        if (tree[ls].lazi != Inf) tree[ls].lazi += x;

        tree[rs].sum += (r - mid) * x; 
        tree[rs].mx += x; tree[rs].mi += x;
        tree[rs].lazs += x;
        if (tree[rs].sx != -Inf) tree[rs].sx += x;
        if (tree[rs].si != Inf) tree[rs].si += x;
        if (tree[rs].lazx != -Inf) tree[rs].lazx += x;
        if (tree[rs].lazi != Inf) tree[rs].lazi += x;

        tree[node].lazs = 0;
    }

    if (tree[node].lazi != Inf) {
        x = tree[node].lazi;
        if (x < tree[ls].mx) {
            tree[ls].sum += (x - tree[ls].mx) * tree[ls].cx;
                        // 顺序不要搞错了！
            if (tree[ls].si == tree[ls].mx) tree[ls].si = x;
            if (tree[ls].mi == tree[ls].mx) tree[ls].mi = x;
            tree[ls].lazx = min (tree[ls].lazx, x);
            tree[ls].mx = tree[ls].lazi = x;
        }

        if (x < tree[rs].mx) {
            tree[rs].sum += (x - tree[rs].mx) * tree[rs].cx;
            if (tree[rs].si == tree[rs].mx) tree[rs].si = x;
            if (tree[rs].mi == tree[rs].mx) tree[rs].mi = x;
            tree[rs].lazx = min (tree[rs].lazx, x);
            tree[rs].mx = tree[rs].lazi = x;
        }

        tree[node].lazi = Inf;
    }

    if (tree[node].lazx != -Inf) {
        x = tree[node].lazx;
        if (x > tree[ls].mi) {
            tree[ls].sum += (x - tree[ls].mi) * tree[ls].ci;
            if (tree[ls].sx == tree[ls].mi) tree[ls].sx = x;
            if (tree[ls].mx == tree[ls].mi) tree[ls].mx = x;
            tree[ls].lazi = max (tree[ls].lazi, x);
            tree[ls].mi = tree[ls].lazx = x;
        }

        if (x > tree[rs].mi) {
            tree[rs].sum += (x - tree[rs].mi) * tree[rs].ci;
            if (tree[rs].sx == tree[rs].mi) tree[rs].sx = x;
            if (tree[rs].mx == tree[rs].mi) tree[rs].mx = x;
            tree[rs].lazi = max (tree[rs].lazi, x);
            tree[rs].mi = tree[rs].lazx = x;
        }

        tree[node].lazx = -Inf;
    }
}

void build (int node, int l, int r) {
    tree[node].lazi = Inf; 
    tree[node].lazx = -Inf;

    if (l == r) {
        tree[node].sum = tree[node].mi = tree[node].mx = a[l];
        tree[node].si = Inf; tree[node].sx = -Inf;
        tree[node].ci = tree[node].cx = 1;
        return ;
    }

    int mid = l + ((r - l) >> 1);
    build (node << 1, l, mid);
    build ((node << 1) + 1, mid + 1, r);
    pushup (node);
}

void modify_sum (int node, int l, int r, int s, int t, long long c) {
        // 跟 pushdown 一样的。
    if (s <= l && r <= t) {
        tree[node].sum += (r - l + 1) * c; 
        tree[node].mx += c; tree[node].mi += c;
        tree[node].lazs += c;
        if (tree[node].sx != -Inf) tree[node].sx += c;
        if (tree[node].si != Inf) tree[node].si += c;
        if (tree[node].lazx != -Inf) tree[node].lazx += c;
        if (tree[node].lazi != Inf) tree[node].lazi += c;
        return ;
    }

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1);
    if (s <= mid) modify_sum (node << 1, l, mid, s, t, c);
    if (t > mid) modify_sum ((node << 1) + 1, mid + 1, r, s, t, c);
    pushup (node);
}

void modify_min (int node, int l, int r, int s, int t, int c) {
    if (tree[node].mx <= c) return ;

    if (s <= l && r <= t && tree[node].sx < c) {
        tree[node].sum += (c - tree[node].mx) * tree[node].cx;
        if (tree[node].si == tree[node].mx) tree[node].si = c;
        if (tree[node].mi == tree[node].mx) tree[node].mi = c;
        tree[node].lazx = min (tree[node].lazx, c);
        tree[node].mx = tree[node].lazi = c;
        return ;
    }

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1);
    if (s <= mid) modify_min (node << 1, l, mid, s, t, c);
    if (t > mid) modify_min ((node << 1) + 1, mid + 1, r, s, t, c);
    pushup (node);
}

void modify_max (int node, int l, int r, int s, int t, int c) {
    if (tree[node].mi >= c) return ;

    if (s <= l && r <= t && tree[node].si > c) {
        tree[node].sum += (c - tree[node].mi) * tree[node].ci;
        if (tree[node].sx == tree[node].mi) tree[node].sx = c;
        if (tree[node].mx == tree[node].mi) tree[node].mx = c;
        tree[node].lazi = max (tree[node].lazi, c);
        tree[node].mi = tree[node].lazx = c;
        return ;
    }

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1);
    if (s <= mid) modify_max (node << 1, l, mid, s, t, c); 
    if (t > mid) modify_max ((node << 1) + 1, mid + 1, r, s, t, c);
    pushup (node);
}

long long query_sum (int node, int l, int r, int s, int t) {
    if (s <= l && r <= t) return tree[node].sum;

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1);
    long long ret = 0;
    if (s <= mid) ret += query_sum (node << 1, l, mid, s, t); 
    if (t > mid) ret += query_sum ((node << 1) + 1, mid + 1, r, s, t);
    return ret;
}

int query_min (int node, int l, int r, int s, int t) {
    if (s <= l && r <= t) return tree[node].mi;

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1), ret = Inf;
    if (s <= mid) ret = min (ret, query_min (node << 1, l, mid, s, t));
    if (t > mid) ret = min (ret, query_min ((node << 1) + 1, mid + 1, r, s, t));
    return ret;
}

int query_max (int node, int l, int r, int s, int t) {
    if (s <= l && r <= t) return tree[node].mx;

    pushdown (node, l, r);
    int mid = l + ((r - l) >> 1), ret = -Inf;
    if (s <= mid) ret = max (ret, query_max (node << 1, l, mid, s, t));
    if (t > mid) ret = max (ret, query_max ((node << 1) + 1, mid + 1, r, s, t));
    return ret; 
}

signed main () {

//  freopen ("1.in", "r", stdin);
//  freopen ("2.out", "w", stdout);

    scanf ("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf ("%lld", &a[i]);

    build (1, 1, n);

    scanf ("%lld", &m);
    while (m--) {
        int opt, l, r;
        scanf ("%lld%lld%lld", &opt, &l, &r);

        if (opt == 1) {
            long long x;
            scanf ("%lld", &x);
            modify_sum (1, 1, n, l, r, x);
        } else if (opt == 2) {
            int x;
            scanf ("%lld", &x);
            modify_max (1, 1, n, l, r, x);
        } else if (opt == 3) {
            int x;
            scanf ("%lld", &x);
            modify_min (1, 1, n, l, r, x);
        } else if (opt == 4) printf ("%lld\n", query_sum (1, 1, n, l, r));
        else if (opt == 5) printf ("%lld\n", query_max (1, 1, n, l, r));
        else printf ("%lld\n", query_min (1, 1, n, l, r));
    } 
    return 0;
}