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

问题转化为每个数有 $[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