P8375 [APIO2022] 游戏

Alex_Wei · 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} 等价描述了每个点当前落在了线段树上的哪个区间。这样就会发现上述做法和其它题解的做法是本质相同的。