自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:05:07，当前版本为作者最后更新于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]);
}