当前位置：首页 > news >正文

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

news 来源：原创 2025/8/5 6:38:37

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

题意：

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

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

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

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

分析

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

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

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

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

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

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

有一个 $t r i c k$ ：稠密图上求一个点作为起点的可达性可以 $bi t se t$ 优化 $b f s$ ，复杂度 $O(\frac{n^2}{w})$ 。 $n$ 为稠密图的点数。
具体的做法是 $b f s$ 过程中开一个 $bi t se t$ ： $n o w$ 维护当前还没有入队的点。每次将队头 $u$ 的出边集合 $E_u$ 和 $n o w$ 取交，然后每次 $_ Find \_ next()$ 找到一个点加入队列。一个点只会入队一次，和 $n o w$ 取交的复杂度 $O(\frac{n^2}{w})$ 。每次花费 $O(\frac{n}{w})$ 的复杂度将一个点入队，复杂度也是 $O(\frac{n^2}{w})$ 。

那么有了这个 $t r i c k$ 我们就可以 $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})$ 。中间能消掉的条件是 $\geq 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 -> tif(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;
}

总结

$D A G$ 可达性统计的复杂度不低于平方，最优为 $/ w$ 。
操作分块后要注意那些信息是可以不维护以减小复杂度的。
稠密图上 $bi t se t$ 优化 $b f s$ 的 $t r i c k$ 要记住。

题意：

分析

总结

相关文章：