题解：P9139 [THUPC 2023 初赛] 喵了个喵 II

min_inf · 2025-10-24 22:15:52 · 题解

问题转化为每个数有 [1,2][3,4] 和 [1,3][2,4] 两种情况，然后有包含关系的连边 2-sat。

我们先不急着优化建图。考虑使用 kosaraju 求 SCC，我们只需要在原图和反图上模拟 DFS，也就是需要每次找到一个和某个区间有包含关系且没访问过的点。

假如我们现在的区间是 [l,r]，我们要找到一个 [L,R] 满足 l<L<R<r，那只需要找 l<L 中 R 最小的；同理，需要 L<l<r<R 只需要找 L<l 中 R 最大的，容易使用线段树维护。

这样就能得到一个更好看常数更小且空间线性的做法。code