【学习笔记】析合树
好嘛，最近新学的算法有点多。我所理解的「退役不留遗憾」就是，想学的算法、想做的题都学了、做了。更高一点的梦想——在赛场上驰骋，这…… 我控制不了哈……
大概解决排列中的连续段问题。
定义
- 本原连续段：是个连续段，且排列 P 的连续段集合里不存在「与之相交且不是包含关系」的连续段。排列 P 的析合树由 P 的所有本原连续段组成。
- 儿子序列：每个儿子体现为值域区间。
- 儿子排列：依照儿子序列离散化得到的排列。
- 合点：儿子排列为顺序或逆序的点。特别的，叶子为合点。
- 析点：非合点。
性质
- 合点：任取儿子序列的一个区间，并集都构成一个连续段。
- 析点：任取儿子序列的一个区间（区间长度 $> 1$），并集都不构成一个连续段。
合点性质显然，析点性质考虑反证：若存在这些个区间，取其中最长的，构成的并集是本原连续段，因为 P 中不存在与它相交且不是包含关系的连续段，但它又不在析合树中，与「析合树由所有本原连续段组成」矛盾。
还是挺直观的。
构造
就学 $O(nlogn)$ 的。（OI-wiki 的图太顶了）
增量法，即挨个加点。用栈维护析合森林。当前加入 x，栈顶为 y。重复下列步骤若干次直到栈空或都不满足。（接下来按顺序判每项，即：若之前都不可，且满足……，则……）
- x 能成为 y 新的儿子（即 y 的最后一个儿子和 x 能成为连续段），把 x 挂入 y 的子树并递归下挂。
- x 能和 y 成为兄弟（即 y 和 x 能成为连续段），新生成点 z 作为 x 和 y 的共有父亲