PQ-Tree

为什么 NOIP 模拟会考到这种东西啊？ PQ-Tree 能解决也恐怕仅能解决如下问题： 对于长度为 $n$ 的排列 $p$，在线地给出 $q$ 个限制，每次给定一个集合 $S$，要求在 $p$ 中，$S$ 中的所有数出现位置构成一个连续段，要求对排列计数。 朴素实现的 PQ-Tree 可以给出一个 ......