由于准备再战XCPC, 因此我要开始复健OI!

图论

2-SAT

感觉之前打oi的时候理解的并不透彻啊. 首先,2-SAT算法的本质是以下两个公式:

因此,当我们遇到一个2-CNF的时候,我们会尝试把其中的所有转化为, 得到的会是和原本公式完全等价的新公式.

你可能会有个疑问: 既然,为什么我要在这里把一块加上呢?看上去即使不加也不会出现问题呀. 这个原因我们下面再解释.

得到新的公式后,我们就进行建图,并且的确同一个SCC内的原子公式必须取相同值,从而我们必然需要从后往前取SCC,这就有了三种情况:

  1. 和在同一个SCC里,此时必然无解.
  2. 在里,在里,并且有.此时当然只能选择.
  3. 在里,在里,但是和没有任何依赖关系,此时随便选一个.

等一下,(3)这里竟然可以随便选一个?那我立刻就想到一种情况啊:比如,此时选了后,可能还有一些原子命题没得到赋值(比如,的大小可能小于的大小,从而导致漏了一些原子命题),所以我们又不得不选,可是选了后又不得不选,这一下子不就出矛盾了么!

为了理解为什么这里不会出矛盾,我们来看一下此时和到底是怎样的关系:

我们重新回到刚才那个问题:为什么添加后还要添加呢?这实际上起到的作用是(我们用表示到有一条路径.):如果,则必然也有.

如果,必然说明,并且根据我们上面说的,这导出了并且.这意味着.也就是说,这两个SCC必然是精确对应着彼此的,选择它们哪个后,另一个都完全被否定了.我们不妨用来表示这种关系.

然而这还是有问题,那为什么不可能出现,然后我们被迫选了的可能性呢?这其实是因为如果以及,必然意味着以及,也就是说必定在和之前,因此这个就没有任何道理被选择了.

现在应该容易给出为何只要和不在同一个SCC,就一定有解的理解了:这个缩点后的图确实比较特殊.这个图一定有个结点,其中每个结点都存在一个与之对应,我们最后一定会从这个节点中选出个结点(每一对都要二选一),使得不存在一个"被选择的点"指向一个"未被选择的点".

我们最后想说明在新得到的图中,一定存在一个"后缀子图"(这名字是我自己编的,但是应该可以理解是什么意思?),使得其恰好完成了上面的选择.为此我们直接倒着拓扑排序开始扩张,如果遇到一个可以加入的SCC就加入.这样做一定可以取出个SCC吗?假设和都没被加入,当前拓扑排序最靠后的位置是,这说明:

  1. 已经被加入了,因此不能被加入.
  2. 的排序在之前,意味着.

可是这意味着,因此应该拓扑排序在之前,因此它应该早就被加入了!

数据结构

莫队

重新学了一下莫队-回滚莫队-二次离线莫队, 总结一下就是:

  1. 当你发现你可以快速扩大或者缩小区间并且计算答案的时候, 进行莫队.
  2. 当你发现可以快速扩大区间, 但很难缩小区间的时候, 进行回滚莫队.
  3. 当你发现扩大区间和缩小区间都带一个额外的复杂度, 尝试二次离线莫队.