8230: [yosupo] Tree - Common Interval Decomposition Tree
[Creator : ]
Description
Given a size-$N$ permutation $P_0, P_1, \cdots, P_{N-1}$,print the common interval decomposition tree corresponding to this permutation. In this question, the terms are defined as follows.
-
An intervalis a set that can be expressed as $\lbrace i\in \mathbb{Z}\ |\ l \leq i \leq r\rbrace $ for some integers $l$ and $r$ ($\ 0 \leq l \leq r <N$). We denote such an interval by interval$[l, r]$.
-
A connected interval is an interval $[l, r]$ such that $\lbrace P_i\ |\ l \leq i \leq r\rbrace$ is also an interval.
-
A strong interval is a connected interval$I$ such that one of $I \subset J$, $J \subset I$, and $I \cap J =\emptyset$ holds for all connected interval $J$.
-
The common interval decomposition tree is a rooted tree expressed as the Hasse diagram of the entire strong intervals for the partial order by inclusion.
-
A linear node is a vertex such that, when its children is arranged in ascending order of their left ends $l$, the union of any consecutive children forms a connected interval.
-
A prime node is a vertex that is not a linear node.
Input
$N$
$P_0\ P_1\ P_2\ \cdots P_{N-1}$
$P_0\ P_1\ P_2\ \cdots P_{N-1}$
Output
$X$
$p_0\ l_0\ r_0\ S_0$
$p_1\ l_1\ r_1\ S_1$
$\vdots$
$p_2\ l_{X-1}\ r_{X-1}\ S_{X-1}$
$X$ is the number of vertices in the common interval decomposition tree. $p_i$( $p_i < i$ ) is the integer numbered to the vertex that is the parent of the $i$-th vertex, or $p_i=-1$ if the $i$-th vertex is a tree root. $[l_i,r_i]$ is the interval corresponding to the $i$-th vertex, and $S_i$ is "linear" if the $i$-th vertex is a linear node or "prime" if it is a prime node.
$p_0\ l_0\ r_0\ S_0$
$p_1\ l_1\ r_1\ S_1$
$\vdots$
$p_2\ l_{X-1}\ r_{X-1}\ S_{X-1}$
$X$ is the number of vertices in the common interval decomposition tree. $p_i$( $p_i < i$ ) is the integer numbered to the vertex that is the parent of the $i$-th vertex, or $p_i=-1$ if the $i$-th vertex is a tree root. $[l_i,r_i]$ is the interval corresponding to the $i$-th vertex, and $S_i$ is "linear" if the $i$-th vertex is a linear node or "prime" if it is a prime node.
Constraints
$1 \leq N \leq 500,000$
$0 \leq P_i < N$
$P_i \neq P_j (i \neq j)$
$0 \leq P_i < N$
$P_i \neq P_j (i \neq j)$
Sample 1 Input
3
0 1 2
Sample 1 Output
4
-1 0 2 linear
0 0 0 linear
0 1 1 linear
0 2 2 linear
Sample 2 Input
4
0 2 1 3
Sample 2 Output
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
Sample 3 Input
10
8 0 9 2 1 4 6 5 7 3
Sample 3 Output
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
5 3 3 linear
5 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