PQ-Tree 瞎扯
Froggy
2021-08-04 19:02:53
前言：这玩意没甚卵用，写写纯属娱乐。
---
## $\mathrm{PQ-Tree}$ 的性质：
$\mathrm{PQ-Tree}$ 通过重新排序子结点来表示排列。
排列中每个元素在 $\mathrm{PQ-Tree}$ 中一个叶子节点表示。
对于非叶子节点，有两类：$P$ 节点的子节点可以被任意序列重新排序。$Q$ 节点的子节点可以按相反的顺序排列。
（乍一看这玩意怎么和析合树这么像/jk）
---
## $\mathrm{PQ-Tree}$ 构建过程：
$\mathrm{PQ-Tree}$ 的构建是在线的。每次操作形如钦定排列中若干元素为关键元素，强制它们必须挨在一起。设它们对应的叶子节点为关键点。
首先预处理出每个节点的 $op$。
$op=1$：子树内无关键点。
$op=2$：子树内全是关键点。
$op=3$：子树内部分是关键点。
设当前 dfs 到的点为 $u$，还有 $lim$ 表示关键点是否需要全部靠左（$lim=1$）/全部靠右（$lim=2$）。
如果 $op=1$ 或 $op=2$，直接返回，无需修改。
将 $u$ 的儿子节点按照 $op$ 分类，设三个集合分别为 $a_1$，$a_2$，$a_3$。
显然，$|a_3|\leq 2$（当有 $lim$ 时 $|a_3|\leq 1$），否则无解。
如果关键点全在同一颗子树内（$|a_2|+|a_3|=1$）并且 $lim=0$，那么 dfs 该子树即可。
否则，
- 如果 $u$ 是 $P$ 类点：
由于 $a_2$ 中的点可以随意排列，所以新建 $P$ 类点 $z$，令其儿子为 $a_2$，父亲为 $u$。
$a_3$ 中的点肯定在 $z$ 的两侧，并且其儿子中的关键点需要强制靠左/靠右。
- 如果 $|a_1|=0$：
将 $u$ 改为 $Q$ 类点。
- 如果 $|a_1|>0$ ：
- 如果有 $lim$：
将 $u$ 改为 $Q$ 类点。
$a_1$ 中的点可以随意排列，新建 $P$ 类点，令其儿子为 $a_1$，父亲为 $u$。
- 如果无 $lim$：
保持 $u$ 为 $P$ 类点。
除 $a_1$ 以外的 $u$ 的儿子不能随意排列，新建 $Q$ 类点，令其儿子为除 $a_1$ 之外 $u$ 的儿子，父亲为 $u$。
- 如果 $u$ 是 $Q$ 类点：
由于儿子只能翻转，所以可以从左往右扫，并维护当前状态。
状态（$now$）：
$now=0$：无关键点出现过。
$now=1$：最后是关键点。
$now=2$：关键点出现过，最后不是关键点。（显然之后不能出现关键点，否则无解）
扫的时候根据儿子的 $op$ 进行决策。
存在 $lim$ 时需要特判一下。
构建的时间复杂度是 $\mathcal{O}(nm)$。
构建过程可能存在可以精简的地方，欢迎指出。
***code：***
```cpp
#define N 1010
const int mod=998244353;
int fac[N];
class PQ_Tree{
private:
int n;
public:
/*
type:
0: P
1: Q
*/
struct node{
vector<int> son;
int type,op;
}t[N<<2];
int tot,rt;
bool OK;
bitset<N> vis;
void init(int _n){
tot=n=_n;rt=++tot;
for(int i=1;i<=n;++i)t[rt].son.push_back(i);
}
void dfs1(int u){
if(u<=n)return (void)(t[u].op=vis[u]?2:1);
t[u].op=0;
for(auto v:t[u].son){
dfs1(v);t[u].op|=t[v].op;
}
}
void dfs2(int u,int lim){
/*
lim:
0: none
1: left
2: right
*/
if(!OK||t[u].op^3)return;
vector<int> a[4];
for(auto v:t[u].son){
a[t[v].op].push_back(v);
}
if((lim>0)+a[3].size()>=3){OK=false;}
if(!lim&&(a[2].size()+a[3].size())<=1){
if(!a[2].empty())dfs2(a[2][0],0);
if(!a[3].empty())dfs2(a[3][0],0);
return;
}
if(t[u].type){
int now=0;
vector<int> S;
if(t[t[u].son[0]].op==2||t[t[u].son.back()].op==1){
reverse(t[u].son.begin(),t[u].son.end());
}
for(auto v:t[u].son){
if(t[v].op==1){
S.push_back(v);
now+=now==1;
}
else if(t[v].op==2){
S.push_back(v);
now+=!now;
if(now==2)OK=false;
}
else{
if(now==2)OK=false;
++now;
dfs2(v,3-now);
S.insert(S.end(),t[v].son.begin(),t[v].son.end());
}
}
if(lim&&now==2)OK=false;
if(lim==1)reverse(S.begin(),S.end());
t[u].son=S;
}
else{
int z=-1;
if(a[2].size()==1)z=a[2][0];
else if(a[2].size()>1)z=++tot,t[z].type=0,t[z].son=a[2];
vector<int> S;
if(!a[3].empty()){
dfs2(a[3][0],2);
S.insert(S.end(),t[a[3][0]].son.begin(),t[a[3][0]].son.end());
}
if(~z)S.push_back(z);
if(a[3].size()>1){
dfs2(a[3][1],1);
S.insert(S.end(),t[a[3][1]].son.begin(),t[a[3][1]].son.end());
}
if(a[1].empty()){
if(lim==1)reverse(S.begin(),S.end());
t[u].type=1,t[u].son=S;
}
else{
if(lim){
t[u].son.clear();
t[u].type=1;
z=a[1][0];
if(a[1].size()>1){
z=++tot,t[z].type=0,t[z].son=a[1];
}
t[u].son.push_back(z);
t[u].son.insert(t[u].son.end(),S.begin(),S.end());
if(lim==1)reverse(t[u].son.begin(),t[u].son.end());
}
else{
z=S[0];
if(S.size()>1)z=++tot,t[z].son=S,t[z].type=1;
t[u].son=a[1],t[u].son.push_back(z);
}
}
}
}
bool Insert(const bitset<N> &B){
vis=B;
dfs1(rt);OK=true;
dfs2(rt,0);
return OK;
}
int calc(int u){
if(u<=n)return 1;
int ans=t[u].type?2:fac[t[u].son.size()];
for(auto v:t[u].son)ans=1LL*ans*calc(v)%mod;
return ans;
}
}T;
```
---
## 例题：
### [CF1552I](https://codeforces.com/contest/1552/problem/I)
计算排列的方案数时可以对每个非叶子节点分开考虑贡献，最后乘起来。
$P$ 类点就是 儿子个数的阶乘，$Q$ 类点就是 $2$。
### [CF243E](https://codeforces.com/contest/243/problem/E)
输出方案就直接在 $\mathrm{PQ-Tree}$ 上中序遍历。
### [Luogu P7341](https://www.luogu.com.cn/problem/P7341)
略。
---
参考资料：
1. [oi-wiki PQ 树](https://oi-wiki.org/ds/pq-tree/#_1)
2. [zaky 的代码](https://www.luogu.com.cn/record/54620462)。