P11369 [Ynoi2024] 弥留之国的爱丽丝（操作分块，DAG可达性trick）

真的神仙题。感觉学到了很多。

题意：

给你一张 $n$ 个结点 $m$ 条边的有向图，点编号为 $1,2,\dots ,n$。每条边的颜色为黑色或白色。一开始所有 $m$ 条边都是黑色的。

你需要进行 $q$ 次操作，有两种操作：

• 1 k：将第 $k$ 条边的颜色反转。
• 2 u v：询问是否能只经过黑色边从 $u$ 到达 $v$。

$2\le n\le 5\times 10^4,1\le m,q\le 10^5,u\ne v$。

分析

首先即使没有一操作，原问题也不弱于 $DAG$ 可达性问题，因此复杂度不可能低于 $O(\frac{nm}{w})$。

如果没有一操作，我们可以缩点后跑 $DAG$ 可达性。但是现在有了一操作，我们不可能每次修改后都跑一次。
想想看哪里有可以突破的地方？
发现我们只会询问 $m$ 个点对的可达关系，而每次拓扑时 $bitset$ 压 $n$ 个点是否可达能够表示出所有 $n^2$ 个点对之间的可达关系，这好像是冗余的。

因此我们考虑 操作分块。设阈值为 $B$，每 $B$ 个操作放到一起处理。
这时候就会有比较好的性质：对于一个块里的所有询问的终点，显然我们只关心所有点能不能到达这些点，因此跑拓扑排序的时候可以将 $bitset$ 的大小压缩至 $O(B)$ 量级。

具体的：
我们考虑将当前块内 $1$ 操作的所有边都先删去，那么剩下的边在块内操作时不会受到影响。将删去边的两端点 $u,v$ 和块内 $2$ 操作的起点终点 $u^{\prime },v^{\prime }$ 称作关键点。那么显然有 $O(B)$ 个关键点。

对于剩下的图 $O(n+m)$ 的跑一遍 $tarjan$ 缩点，然后对形成的 $DAG$ 在 $O(\frac{(n+m)B}{w})$ 的复杂度内跑一遍拓扑，求出缩点后关键点与关键点之间的可达关系。那么我们就可以将原来的图压缩成只有$O(B)$ 个关键点的新图。

接下来考虑怎样处理块内操作：
对于操作 $1$，等价于关键点之间的删边和加边。我们另开一类 $bitset$ $g_{i,j}$ 表示增加的出边集合，其中 $j$ 一维的大小为关键点个数。那么可以 $O(1)$ 在 $g$ 上修改。
对于操作 $2$，等价于判断某一关键点能否到达另一关键点。朴素的做法是从 $u^{\prime }$ 开始 $bfs$，复杂度 $O(|E|)$。但是这里我们压缩出的新图非常稠密，$|E|$ 可以取到 $B^2$。

有一个 $trick$：稠密图上求一个点作为起点的可达性可以 $bitset$ 优化 $bfs$，复杂度 $O(\frac{n^2}{w})$。$n$ 为稠密图的点数。
具体的做法是 $bfs$ 过程中开一个 $bitset$：$now$ 维护当前还没有入队的点。每次将队头 $u$ 的出边集合 $E_u$ 和 $now$ 取交，然后每次 $.\_Find\_next()$ 找到一个点加入队列。一个点只会入队一次，和 $now$ 取交的复杂度 $O(\frac{n^2}{w})$。每次花费 $O(\frac{n}{w})$ 的复杂度将一个点入队，复杂度也是 $O(\frac{n^2}{w})$。

那么有了这个 $trick$ 我们就可以 $O(\frac{B^2}{w})$ 求一次询问。

总复杂度：$O(\frac{q}{B}(n+m)+\frac{q(n+m)B}{Bw}+q\frac{B^2}{w})=O(\frac{q}{B}(n+m)+\frac{q(n+m)}{w}+q\frac{B^2}{w})$。中间能消掉的条件是 $B\ge w$，将第一个和第三个式子取等得到 $B$ 取 $\sqrt[3]{(n+m)w}$ 最优。实测 $B=200$ 比较优秀。

复杂度上界还是 $O(\frac{q(n+m)}{w})$。

CODE：

// 确实是神仙题啊
// 可做的原因在于：不需要统计所有点对的可达性，只关心询问点的可达性
// 操作分块后,toopsort 时就可以只压 O(B) 个点
// 然后加边时只关注加的边两个端点是否可达，因此还是 O（B）个。 同时稠密图的bfs 可以bitset 优化到 n^2 / w
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 5e4 + 10;
const int M = 1e5 + 10;
const int L = 405;
int n, m, q, u[M], v[M];
int dfn[N], low[N], dfc, bel[N], Stack[N], Top, ct;
bool ins[N], bok[M]; // bok[i] = 1 的边不能用
int ans[M], exs[M];
struct edge {
	int v, last;
} E[M];
int head[N], tot;
inline void add(int u, int v) {E[++ tot].v = v; E[tot].last = head[u]; head[u] = tot;}
struct OP {int o, x, y;} opt[M];
void tarjan(int x) {
	dfn[x] = low[x] = ++ dfc; Stack[++ Top] = x; ins[x] = 1;
	for(int i = head[x]; i; i = E[i].last) {
		if(!exs[i] || bok[i]) continue;
		int v = E[i].v;
		if(!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);
		else if(ins[v]) low[x] = min(low[x], dfn[v]);
	}
	if(dfn[x] == low[x]) {
		int y; ct ++;
		do {y = Stack[Top --]; ins[y] = 0; bel[y] = ct;} while(y != x);
	}
}
vector< int > G[N];
int in[N], vec[N], len, idx[N], ID[N];
bitset< L > f[N], g[N]; // 可达性
inline void toopsort() {
	queue< int > q;
	for(int i = 1; i <= ct; i ++ ) 
		if(!in[i]) q.push(i);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto v : G[u]) {
			f[v] |= f[u];
			in[v] --; if(!in[v]) q.push(v);
		}
	}
}
inline int bfs(int s, int t) { // s -> t
	if(s == t) return 1;
	bitset< L > now; now.set();
	queue< int > q; q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		bitset< L > tmp = (now & (f[u] | g[u]));
		for(int p = tmp._Find_first(); p < L; p = tmp._Find_next(p)) {
			if(idx[p] == t) return 1;
			q.push(idx[p]); now.reset(p);
		}
	}
	return 0;
}
inline void solve(int l, int r) { // 处理 [l, r] 的操作
	for(int i = l; i <= r; i ++ ) 
		if(opt[i].o == 1) bok[opt[i].x] = 1;
	dfc = 0; ct = 0;
	for(int i = 1; i <= n; i ++ ) dfn[i] = low[i] = 0, ins[i] = 0;
	for(int i = 1; i <= n; i ++ ) {
		if(!dfn[i]) tarjan(i);
	}
	len = 0;
	for(int i = l; i <= r; i ++ ) {
		if(opt[i].o == 1) vec[++ len] = bel[u[opt[i].x]], vec[++ len] = bel[v[opt[i].x]];
		else vec[++ len] = bel[opt[i].y];
	}
	sort(vec + 1, vec + len + 1);
	len = unique(vec + 1, vec + len + 1) - (vec + 1);
	for(int i = 1; i <= len; i ++ ) {
		idx[i] = vec[i]; ID[vec[i]] = i; // 编号
		f[vec[i]].set(i);
	}
	for(int i = 1; i <= n; i ++ ) {
		for(int j = head[i]; j; j = E[j].last ) {
			if(bok[j] || !exs[j]) continue;
			if(bel[i] != bel[E[j].v]) G[bel[E[j].v]].pb(bel[i]), in[bel[i]] ++;
		}
	}
	toopsort();
	for(int i = l; i <= r; i ++ ) {
		if(opt[i].o == 1) 
			if(exs[opt[i].x]) g[bel[u[opt[i].x]]].set(ID[bel[v[opt[i].x]]]);
	}
	for(int i = l; i <= r; i ++ ) { // 处理询问
		if(opt[i].o == 1) {
			exs[opt[i].x] ^= 1; bok[opt[i].x] = 0;
 			if(!exs[opt[i].x]) g[bel[u[opt[i].x]]].reset(ID[bel[v[opt[i].x]]]);
			else g[bel[u[opt[i].x]]].set(ID[bel[v[opt[i].x]]]);
		}
		else ans[i] = bfs(bel[opt[i].x], bel[opt[i].y]);
	}
	for(int i = 1; i <= ct; i ++ ) {
		G[i].clear(); f[i].reset(); g[i].reset();
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= m; i ++ ) {
		scanf("%d%d", &u[i], &v[i]);
		exs[i] = 1; add(u[i], v[i]);
	}
	for(int i = 1; i <= q; i ++ ) {
		scanf("%d%d", &opt[i].o, &opt[i].x);
		if(opt[i].o == 2) scanf("%d", &opt[i].y);
	}
	int B = 200;
	for(int i = 1; i <= q; i += B ) solve(i, min(q, i + B - 1)); 
	for(int i = 1; i <= q; i ++ ) 
		if(opt[i].o == 2) puts(ans[i] == 1 ? "YES" : "NO");
	return 0;
}

总结

1. $DAG$ 可达性统计的复杂度不低于平方，最优为 $/w$。
2. 操作分块后要注意那些信息是可以不维护以减小复杂度的。
3. 稠密图上 $bitset$ 优化 $bfs$ 的 $trick$ 要记住。