P11191 题解

Register_int · 2024-10-13 18:48:01 · 题解

鲜花：24+0+6+100，竞选全场最搞笑选手。

考虑对于每个 a_i，预处理出来“若要释放这个点，至少需要 w_i\sim i 的操作”的 w_i。有个很暴力的求法：显然若一个点一步就能到 1，那么 w_i=i。否则将这个点的 w_i 和他的所有后继取 \max 即可。求出来 w_i 后可以变成二维偏序问题，扫描线一下就做完了。

考虑优化求 w_i 的部分。根号分治，设阈值为 B，若 a_i 度数 <B 直接暴力更新。算出一个点后，用这个点更新所有度数 \ge B 的点。复杂度是 O(nB+n\times\frac nB) 的。那么做完了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

vector<int> g[MAXN], rg[MAXN]; int d[MAXN], B;

int n, m, p, q, a[MAXN]; vector<pair<int, int>> f[MAXN]; bool isp[MAXN];

int tw[MAXN], w[MAXN], rev[MAXN], lst[MAXN], c[MAXN], ans[MAXN];

inline void add(int k, int x) { for (int i = k; i <= p; i += i & -i) c[i] += x; }
inline int ask(int k) { int res = 0; for (int i = k; i; i &= i - 1) res += c[i]; return res; }

int main() {
//  freopen("./show/show5.in", "r", stdin);
//  freopen("show5.out", "w", stdout);
    scanf("%*d%d%d%d%d", &n, &m, &p, &q), B = sqrt(m);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v); if (v == 1) isp[u] = 1;
        g[u].emplace_back(v), d[u]++;
    }
    for (int u = 1; u <= n; u++) {
        if (d[u] < B) continue;
        for (int v : g[u]) rg[v].emplace_back(u);
    }
    for (int i = 1; i <= p; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= p; i++) {
        if (isp[a[i]]) w[i] = i;
        else if (d[a[i]] >= B) w[i] = tw[a[i]];
        else for (int v : g[a[i]]) w[i] = max(w[i], rev[v]);
        rev[a[i]] = w[i];
        for (int v : rg[a[i]]) tw[v] = max(tw[v], w[i]);
    }
    for (int i = 1, l, r; i <= q; i++) scanf("%d%d", &l, &r), f[r].emplace_back(l, i);
    for (int i = 1, cnt = 0; i <= p; i++) {
        if (lst[a[i]]) add(lst[a[i]], -1), cnt--;
        if (w[i]) add(w[i], 1), lst[a[i]] = w[i], cnt++;
        for (pair<int, int> x : f[i]) ans[x.second] = n - 1 - cnt + ask(x.first - 1);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}