题解【P6378 [PA2010] Riddle】

补了一个巨坑，2021 夏令营的历史遗留产物。

考虑转化成 $\text{2-sat}$ 模型，每个点有两种情况，关键点或不是关键点。我们令 $x$ 表示 $x$ 是关键点，$x'$ 则不是关键点。

对于原图的一条边 $(u,v)$，则可以抽象成【两个条件至少满足一个】这一条件限制，连边 $u'\to v,v'\to u$。

那么，【每一个部分都有一个关键点】这一条件限制应该怎样满足呢？

最暴力的想法是，枚举每一个点，然后暴力向它所在的部分的除自己以外所有的点连边，复杂度 $\Theta(n^2)$。考虑优化。

考虑新建虚拟节点加快建边速度，$i$ 要连向 $[1,i-1]$ 和 $[i+1,n]$ 这两个区间，可以分开考虑。

对于区间 $[i+1,n]$，假设说 $i+1$ 号节点已经连上了 $[i+2,n]$，那么我们只需连一条 $i\to i+1$ 的有向边即可，边的关系是传递的。

但 $i+1$ 管辖的范围只是 $[i+2,n]$，所以特别的，我们再连一条 $i\to i'+1$ 的边即可。反过来也是一样，这便是【前后缀和优化建图】的经典 $\texttt{trick}$。

很可惜，这是个假做法。我们连了 $i\to i+1$，但是又连了 $i+1\to i'$，可以得到 $i\to i'$，这不就相当于连了所有的点吗（害怕）。

那么怎么办呢？

我们可以对于每一个 $i$ 新建一个克隆节点 $pre_i$，每一个 $i'$ 新建一个克隆 $suf_{i'}$ 即可，我们连 $i\to pre_i$，$suf_{i'}\to i'$，直接把 $pre$ 和 $suf$ 当成节点来连边，这就是对的了！

代码就不放了，写的都一样/qd

AC 记录：$\textbf{QwQ}$。