析合树（permutation tree）

(Updated: )
(6 mins to read)

仅限于解决排列中与连续段相关的问题，局限性比较大，虽然平凡序列也能做，但是会复杂很多一些定义：段：该区间排序后值域连续本原段：与其它连续段只有包含和相离的关系，没有相交关系儿子排列：各个儿子离散化后的编号形成的排列合点：儿子排列为顺序或逆序（叶子也认为是合点）析点：不是合点的节点

  • 合点的儿子序列的任意子区间都是一个连续段
  • 析点的儿子序列的任意长度大于1的子区间都不是连续段（否则该区间就是一个本原段）

析合树就是由若干本原段构成，且每个本原段是合点和析点中的一种。增量构造$O(n\log n)$，维护前$i$个结点的栈，然后考虑当前结点$P_i$​

  1. 栈顶为合点且可以成为它的儿子
  2. 栈的某个后缀可以生成一个合点作为父亲
  3. 栈的某个后缀可以生成一个析点作为父亲

最主要的一个辅助工具是快速查询$[j,i]$这个区间是否是连续段，由于是排列，所以只需要检查$Q_j=\max\limits_{i\lek\le j}P_k-\min\limits_{i\le k\le j}P_k-(i-j)=0$，又注意到$Q_j\ge 0$，因此用单调栈和线段树维护$Q$，值为0的点就可以作为连续段的左端点。

代码解释：节点数要开两倍$id_i$​：表示排列中第$i$个数在析合树中的编号$L_i,R_i$​：编号为$i$的点在排列中对应的下标范围$SR_i$​：编号为$i$的点当前最靠右（最后加入）的儿子的$L$$type_i$​：编号为$i$的点的类型，1表示合点，0表示析点$rt$：析合树的根节点$cnt$：析合树的节点数$askmn$：单点查询一个点的$Q$，用于检查是否为连续段$askpos$：找到最靠左的可以与当前右端点构成连续段下标对于当前点$i$，先维护好$Q$序列

  1. 如果能与栈顶最右的儿子形成连续段就作为它的儿子（此时栈顶必然是合点，因为析点不可能有子区间是连续段）
  2. 如果能与栈顶构成连续段，则生成一个合点
  3. 否则如果某个后缀是连续段，就生成一个析点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
namespace Ptree {
const int M = N<<1, LOG = 17;
int id[M], L[M], R[M], SR[M], type[M], rt, cnt;
int stk[M], stk1[M], stk2[M], tp, tp1, tp2;
vector<int> G[M];
inline void add(int x, int y) { G[x].push_back(y); }
void work() {
  build(1, 1, n);
  for(int i=1; i<=n; i++) {
    while(tp1 && a[i]<=a[stk1[tp1]]) {
      upd(1, stk1[tp1-1]+1, stk1[tp1], a[stk1[tp1]]);
      --tp1;
    }
    upd(1, stk1[tp1]+1, i, -a[i]);
    stk1[++tp1] = i;
    while(tp2 && a[i]>=a[stk2[tp2]]) {
      upd(1, stk2[tp2-1]+1, stk2[tp2], -a[stk2[tp2]]);
      --tp2;
    }
    upd(1, stk2[tp2]+1, i, a[i]);
    stk2[++tp2] = i;
    id[i] = ++cnt;
    L[cnt] = R[cnt] = i;
    int pos = askpos(1), now = cnt;
    while(tp && L[stk[tp]]>=pos) {
      if(type[stk[tp]] && askmn(1, SR[stk[tp]])==0) {
        R[stk[tp]] = i, SR[stk[tp]] = L[now], add(stk[tp], now), now = stk[tp--];
      } else if(askmn(1, L[stk[tp]])==0) {
        type[++cnt] = 1;
        L[cnt] = L[stk[tp]], R[cnt] = i, SR[cnt] = L[now];
        add(cnt, stk[tp--]), add(cnt, now);
        now = cnt;
      } else {
        add(++cnt, now);
        do {
          add(cnt, stk[tp--]);
        } while(tp && askmn(1, L[stk[tp]])!=0);
        L[cnt] = L[stk[tp]], R[cnt] = i, add(cnt, stk[tp--]);
        now = cnt;
      }
    }
    stk[++tp] = now;
    upd(1, 1, i, -1);
  }
  rt = stk[1];
}
} //namespace Ptree

  • Codeforces 526F – Pudding Monsters查询一个排列的连续段个数，显然只需要完成Q序列的维护即可

  • CERC 17 Problem I – Instrinsic Interval给出一个排列，每次查询给出$l,r$，问你最短的包含该区间的连续段的左右端点我们先求出LCA，如果是析点，说明答案只能是LCA的左右端点；否则可以在儿子序列中找到一个最小的包含$l,r$的子区间，实质上利用倍增跳到LCA的儿子即可