浅谈 Kosaraju 的一类运用 (2)

我们在上篇文章中处理了一些 work，接下来我们可以去做上上篇文章末尾的例题了。

首先进行一些最开始的操作，先假装每个只有两种，注意到只要不存在 l_1<l_2<r_2<r_1 使得 a_{l_i}=a_{r_i} 即可。

那我们现在回归原问题。我们考虑人工强制钦定是 ((1,2),(3,4)) 还是 ((1,3),(2,4))，注意到 ((1,4),(2,3)) 是不可能的，因为包含了。

那就是 2-SAT 了，限制是区间不能相交，我们这时候观察上篇文章（链接在这篇文章顶部），发现提到的三种做法中，主席树和 CDQ 分治直接优化建图即可，但是最后一种常数最小的做法做不了，这多多少少有点遗憾……吗？

还是考虑 Kosaraju，那么问题和上上篇文章（链接在这篇文章顶部）一样转化为遍历问题，就可以套上去了，空间仍然线性。

另外其实一维版本和二维版本的问题，Kosaraju 都没有造成任何复杂度提升。

因为一维版本最后提供的例题每次连边长度相等，可以分块然后前后缀优化建图，二维版本的例题就是这题，用不用 Kosaraju 都是单 \log，Kosaraju 常数能小很多而已。

Kosaraju 缩点算法你好菜。