「题解」洛谷 - P7416 [USACO21FEB] No Time to Dry P

Mohao2025/10/30大约 3 分钟

「题解」洛谷 - P7416 [USACO21FEB] No Time to Dry P

某一个神秘的夜晚， $\tt{louisdlee}$ 发来了一道神秘的题目，遂做之。

题目

假设存在一个全是 $0$ 的区间 $[1, n]$ ，若要把它覆盖成 $[a_1, a_2, \ldots a_n]$ ，每次覆盖都能选中连续的一段子数组，把颜色设为 $x$ ，但是要求「颜色小的不能覆盖颜色大的」，对于每一个查询 $[l, r]$ 求最小覆盖次数。

首先我们肯定要思考一个最优的覆盖策略，否则一切都无从谈起。

我们要想办法快速求出「对于 $i$ 来说，上一个能把它染色的节点 $p_i$ 」，记上一个值为 $a_i$ 的节点为 ${lst}_i$ ， $p_i$ 显然是满足不存在 $j \in [lst_k, i]$ 使得 $a_j < a_i$ 的某个 ${lst}_k$ 节点。然后为了判断这段区间内有没有比 $a_i$ 更小的数，这里使用单调栈维护。最后我们不难得出答案就是满足 $i \in [l, r] \land p_i < l$ 的节点数量。

于是在这里我们把问题转化为了求区间内小于某个数的节点数量，看过上一期的同学们想必非常熟悉这个东西。我们在 HH 的项链那里也有查询区间 $[l, r]$ 内所有小于 $l$ 的下标的次数和的操作。

显然我们发现，可持久化权值线段树可以完美地做到查询区间内小于某个数值的元素的次数和，于是我们直接把那题的代码抄一下改一下就做完了。

代码

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

constexpr int N = 2e5 + 10;

struct HJT {
    int cntNodes, root[N];
    struct Node {
        int l, r;
        int cnt;
    } tr[32 * N];
    void modify(int &u, int v, int l, int r, int x) {
        u = ++cntNodes;
        tr[u] = tr[v];
        tr[u].cnt++;
        if (l == r) return;
        int mid = (l + r) / 2;
        if (x <= mid) {
            modify(tr[u].l, tr[v].l, l, mid, x);
        } else {
            modify(tr[u].r, tr[v].r, mid + 1, r, x);
        }
    }
    int query(int u, int v, int l, int r, int ql, int qr) {
        if (ql <= l and r <= qr)
            return tr[v].cnt - tr[u].cnt;
        int mid = (l + r) / 2;
        int res = 0;
        if (ql <= mid)
            res += query(tr[u].l, tr[v].l, l, mid, ql, qr);
        if (qr > mid)
            res += query(tr[u].r, tr[v].r, mid + 1, r, ql, qr);
        return res;
    }
    int kth(int u, int v, int l, int r, int k) {
        if (l == r) return l;
        int res = tr[tr[v].l].cnt - tr[tr[u].l].cnt;
        int mid = (l + r) / 2;
        if (k <= res)
            return kth(tr[u].l, tr[v].l, l, mid, k);
        return kth(tr[u].r, tr[v].r, mid + 1, r, k - res);
    }
} hjt;

int a[N];
int p[N];
int lst[N];

signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        while (not stk.empty() and a[stk.top()] >= a[i])
            stk.pop();
        int l = lst[a[i]];
        if (l > 0 and (stk.empty() or stk.top() < l))
            p[i] = l;
        stk.push(i);
        lst[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        hjt.modify(hjt.root[i], hjt.root[i - 1], 0, n, p[i]);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << hjt.query(hjt.root[l - 1], hjt.root[r], 0, n, 0, l - 1) << "\n";
    }
}
auto FAST_IO = cin.tie(nullptr)->sync_with_stdio(false);

显然是十分好的题目，感谢 $\tt{louisdlee}$ 哥哥捏。

以上。