PQ Tree

                          PQ Tree
                        philipsweng

PQ树是用来解决将序列全排列，使得某些关键点排列在一起的问题的数据结构。

具体操作。
我们将PQ树上的点分为P,Q两种类型，P类型表示其儿子可以任意顺序排列，Q类型表示其儿子可以以从左到右排列或者从右到左排列。
并且PQ树上的一个叶子表示的就是全排列中的一个元素。
最终的可行方案是PQ树的先序遍历

当我们接受到一组新的点集S,表示我们需要将S中的点紧凑地排列在一起。
我们对于每个点维护一个值Bel,若此点的子树的叶子全都为关键点，则Bel= 1,若子树中没有关键点则为0,否则为2

我们考虑如何调整树的形态使得当前约束合法。
我们对当前节点的状态分类讨论。
我们的目的是要让节点子树中的关键节点都排列在一起。
若为Q类节点，
则我们从左到右判断Q的儿子的信息，
我们继续分类讨论儿子的信息
设当前节点的边集为E(E有顺序)设新排列为E1
0：若我们之前有一个儿子不为0，则之前的关键节点到这里已经结束了。E1中加入此节点
1：若之前已经关键节点排列结束了，我们现在又多一个关键节点，则非法。否则在E1中加入此节点。
2：非法情况同1.值得注意的是，假如出现了2，且之前出现过非0点，我们关键节点的排列也要结束。同时，我们在E1中加入此节点的儿子靠左(或靠右)的顺序(此步递归处理，因为我们需要其子树都要靠左（或靠右）)

若当前为P类节点，
我们需要新建一个Q类节点T,设T的边集为L。
我们先找到第一个2号节点P，此节点要全部靠右。我们在L中加入P的儿子全部靠右后的顺序。
接着我们新建一个P类节点T1.
E中的1号节点全都连入T1的边集中。
我们再将T1加入L中（注意L是有顺序的）
我们再把接下来的2号节点P1，此节点要全部靠左。我们在L中加入P1的儿子全部靠左后的顺序。
我们将T加入E1中。
最后再将E中的0号节点全部加入E1中。

我们现在考虑一个函数
RotateL(X,E)
表示我们要讲X的子树中的关键节点全部连续地靠在最左边并加入E中。
我们仍然需要分类讨论X的情况。
很显然若X有多于1个2号节点，则此函数非法。
否则
若X为Q类节点，T为X的边集
因为Q类节点可以左右翻转，所以若我们从左到右不行，我们将边集翻转后再做一遍。
首先，若T中1号节点并不是连续地排列在T的最左边，则非法。否则我们往E中按顺序加入T中的1号节点。
紧接着，我们需要T中的2号节点皆在1号节点后面。并且我们需要其全都靠左。那么我们递归处理RotateL(P2，E)
接下来我们只需要将0号节点插入E中即可。

若X为P类节点。
我们新建一个P类节点Y.
将T中1号节点全部插入Y的边集中。
我们再将Y加入E中。
接着我们需要递归处理RotateL(P2，E)，其中P2为T中的2号节点。
我们再新建一个P类节点Z
将T中0号节点全部插入Z的边集中。
再将Z加入E中。

所有的操作就这样。

PQ树的精髓在于其将节点分为两类，并分类讨论。注意到了实质。
习题：CF243E