公共区间分解树（Common Interval Decomposition Tree）

问题描述

给定一个大小为 $N$ 的排列 $P = (P_0, P_1, \dots, P_{N-1})$。
构造该排列的公共区间分解树（Common Interval Decomposition Tree）。

定义如下：

• 区间：形如 $[l, r] = \{ i \in \mathbb{Z} \mid l \le i \le r \}$，其中 $0 \le l \le r < N$。
• 连通区间：一个区间 $I$，使得 $\{ P_i \mid i \in I \}$ 本身也是一个区间（即值集连续）。
• 强区间：一个连通区间 $I$，满足对任意其他连通区间 $J$，要么 $J \subset I$，要么 $I \subset J$，要么 $I \cap J = \emptyset$。
• 公共区间分解树：以所有强区间为节点的有根树，按包含关系构成偏序（子集为后代），根为整个区间 $[0, N-1]$；该树的 Hasse 图即为所求。
• 线性节点：一个非根节点 $v$，若其所有子节点按左端点升序排列后，其子节点对应的区间并集仍为一个连通区间，则 $v$ 是线性节点。
• 素数节点（prime node）：非线性节点（即既非叶也非线性）。

输出该树的结构：

• $X$：树中顶点总数；
• 对每个顶点 $i$（$0 \le i < X$）：
  • $p_i$：父节点编号（若为根则 $p_i = -1$）；
  • $l_i, r_i$：该节点对应的区间 $[l_i, r_i]$；
  • $S_i$：字符串 "linear" 或 "prime"，表示该节点类型。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq P_i < N$
• $P_i \ne P_j$（$i \ne j$），即 $P$ 是排列

输入

$N$
$P_0\ P_1\ \cdots\ P_{N-1}$

输出

$X$
$p_0\ l_0\ r_0\ S_0$
$p_1\ l_1\ r_1\ S_1$
:
$p_{X-1}\ l_{X-1}\ r_{X-1}\ S_{X-1}$

其中：

• $p_i = -1$ 表示根；
• $S_i$ 为字面量 "linear" 或 "prime"（不含引号）。

3
0 1 2

4
-1 0 2 linear
0 0 0 linear
0 1 1 linear
0 2 2 linear

4
0 2 1 3

6
-1 0 3 linear
0 0 0 linear
0 1 2 linear
2 1 1 linear
2 2 2 linear
0 3 3 linear

10
8 0 9 2 1 4 6 5 7 3

16
-1 0 9 prime
0 0 0 linear
0 1 1 linear
0 2 2 linear
0 3 9 linear
4 3 4 linear
4 3 4 linear
5 4 4 linear
4 4 4 linear
4 5 9 linear
8 5 8 linear
9 5 5 linear
9 6 7 linear
11 6 6 linear
11 7 7 linear
9 8 8 linear
8 9 9 linear