自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:38:33，当前版本为作者最后更新于2023-04-27 21:05:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8375 [APIO2022] 游戏

堪称神题。

注意到如果形成环，则环上的点和主链 $0\to 1\to\cdots \to k - 1$ 的交是一段子链 $L\to L + 1 \to \cdots \to R$，且 $R\rightsquigarrow L$。

考虑环上的一条边 $i\to i + 1$，若子链包含该边，说明 $[i + 1, k)$ 可达 $[1, i]$。

接下来是一步非常厉害的操作。我们维护两个点集：可达 $[1, i]$ 的点集 $S_1$ 和 $[i + 1, k)$ 可达的点集 $S_2$。这样，如果最终子链不包含 $i\to i + 1$，则环上的所有点一定同时属于 $S_1$ 或同时属于 $S_2$。否则：

• 若环上有同时属于 $S_1$ 和 $S_2$ 的点，显然存在经过 $i\to i + 1$ 的环。
• 若环上有属于 $S_1$ 的点和属于 $S_2$ 的点，通过调整法总可以得到经过 $i\to i + 1$ 的环。
• 根据 $S_1$ 和 $S_2$ 的定义，不存在不属于 $S_1$ 且不属于 $S_2$ 的点。

设一个点的状态为 $0$（不属于 $S_1$ 和 $S_2$），$1$（属于 $S_1$）或 $2$（属于 $S_2$），那么根据上述性质，只有当一条边的两端状态均为 $1$ 或均为 $2$ 时，才需要递归进入对应子区间。又因为 $S_1$ 和 $S_2$ 不交（有交就游戏结束了），这启发我们采用分治：对每个区间 $I = [l, r]$，维护图 $G_I$ 表示可能对点的状态产生影响的边。将 $u\to v$ 加入 $G_I$ 时：

• 若 $u$ 的状态为 $2$ 且 $v$ 的状态为 $1$，则游戏结束。
• 否则，若 $u$ 的状态为 $2$，则从 $v$ 开始在图上 DFS，遇到状态为 $2$ 的点则返回，那么只会遇到状态为 $0$ 的点（如果遇到状态为 $1$ 的点，则 $v$ 的状态为 $1$，矛盾），将其状态改为 $2$。并将遍历到的所有边从 $G_I$ 中删除（没有用了，不会再改变点的状态，即两端状态相同）下放至左子区间，即 $G_{[l, mid]}$。同时将 $u\to v$ 下放至 $G_{[l, mid]}$（两端均为 $2$）。
• 类似地，若 $v$ 的状态为 $1$，则从 $u$ 开始在 反图 上 DFS，遇到状态为 $1$ 的点则返回，遇到状态为 $0$ 的点将其状态改为 $1$，并将遍历到的所有边从 $G_I$ 中删除，下放至右子区间 $G_{(mid, r]}$。同时将 $u\to v$ 下放至 $G_{(mid, r]}$（两端均为 $1$）。

正确性很好理解：根据之前的性质，对于一条边，只有其两端状态相同时，它才可能出现在子链不包含 $mid\to mid + 1$ 的环上，即递归至对应子区间。

很明显地，一个点在同一层只会在一个区间的 $G$ 内：它在父区间的状态决定了它递归进哪个子区间。同理，一条边在一层最多出现一次，且任意时刻只会出现在一个区间：只有它对父区间的点的状态不会再产生影响的时候，才会被下放至子区间。

梳理一下整道题的核心思路：考虑假设环经过 $i\to i + 1$，那我们只关心一个点能否到达 $[1, i]$，以及是否由 $[i + 1, k)$ 可达。我们发现，如果一条边还有可能对点的状态产生影响，就一定不会出现在不经过 $i\to i + 1$ 的环上。若不会对点的状态产生影响，那么它两侧的点要么均可达 $[1, i]$，要么均由 $[i + 1, k]$ 可达。基于此，容易设计类线段树的分治算法。

还有一个小问题：如果环和主链无交边怎么办？考虑将所有边的 $u$ 加 $1$，若 $v \geq k$ 则 $v$ 加 $1$，并认为主链为 $0\to 1\to \cdots \to k$，则原图所有以关键点（编号小于 $k$ 的点）开头，以关键点结尾且中间不经过关键元素的路径的开头编号均增加 $1$，因此原图的符合要求的环在变换后的图上和主链有交。

实现是简单的：记录 $st_{d, i}$ 表示 $i$ 在第 $d$ 层的状态，用邻接链表存图（每个点在一层只会有一个 $head$）。时空复杂度均为 $\mathcal{O}(m\log n)$。代码。

尝试进一步简化算法：直接维护原图和反图。DFS 到点 $u$ 说明它的所有不小于 $d$ 层的状态均不为 $0$。此时对于原图或反图的出边 $u\to v$，若 $v$ 在某个小于 $d$ 层的状态和 $u$ 不同，说明该边还未被下放至当前区间，直接跳过。对所有 $st_{*, i}$ 压位即可快速判断。这样，空间复杂度优化至 $\mathcal{O}(m)$。代码。

仔细思考可知 $st_{*, i}$ 等价描述了每个点当前落在了线段树上的哪个区间。这样就会发现上述做法和其它题解的做法是本质相同的。