析合树小结

部分参考了OI-Wiki。

为了方便，认为下文说的所有内容都在排列上

定义

连续段：一个连续段是一个区间\([l,r]\)，满足值域连续，也就是\(\max-\min+1=r-l+1\)。

连续段的交并差：就是集合的交并差。容易发现两个相交连续段的交，并，差都是连续段。

本原连续段：不存在另一个连续段和它有交且互不包含。

析合树：由本原连续段构成的一个树形结构，树上每个点都是一个连续段。

儿子序列：析合树上一个点的儿子是按照下标顺序排列的，按照顺序形成了一个序列。

合点：一个点所有儿子的值域递增或递减的点叫作合点，叶子（单点的区间）也是一个合点

析点：不是合点的点叫作析点

性质

对于一个合点，它的儿子序列的所有子区间都是一个连续段

对于一个析点，它的儿子序列的所有(长度不为1的)子区间都不是一个连续段

第一条显然，第二条考虑如果存在一个极长子区间是连续段，那么这个子区间应该也是一个本原连续段。

构造

考虑增量法，假设我们有[1..i-1]的析合森林，现在要求[1..i]的析合森林。

我们把析合森林的树根按顺序存到栈里。

首先建一个[i,i]的结点作为当前结点，反复执行如下操作：

如果当前结点能作为栈顶的子结点，要求栈顶不是叶子，且是合点，并且这个点的区间作为下一个儿子依然满足顺序/逆序，那么把当前结点作为栈顶的子结点，把栈顶拿出来作为当前结点。

否则判断是否可以把栈顶连续的尽量少的一些结点和当前结点合并成一个连续段。

如果栈顶和当前结点能合并，就用一个合点连着这两个点。

否则从栈顶开始往下找，如果能合并成一个连续段就用一个析点合并这些点。

如果合并成功了，就把这些点从栈里移出来，并用合并得到的新点作为当前结点。

否则把当前结点压进栈里，退出。

这样最坏是\(O(n^2)\)的，因为有可能遍历了整个栈还不能合并。考虑优化。

考虑当前结点是\([l,i]\)这个区间，计算\([1,l-1]\)中最大的\(j\)表示\([j,i]\)是一个连续段，如果\(j\)存在，栈中一定存在一个区间左端点为\(j\)，合并到这个区间就可以了。

证明如下：

考虑\(j\)所在的区间\([x,y]\)，这个区间一定是连续段。

如果\(j\)不是左端点，根据性质得\([j,y],[x,i]\)是连续段。

如果\([x,y]\)是栈顶，则可以把\([l,i]\)作为\([x,y]\)这个结点的下一个儿子，不会到合并这一步来。

否则根据性质得\([y+1,i]\)是连续段且\(y+1\lt l\)，\(j\)一定不是最大的。

所以\(j\)一定是左端点。

于是这样就构造完了，总共的循环次数和是\(O(n)\)的。

考虑如何计算\(j\)。

记\(i\)出现的位置为\(a_i\)，则\(a_i\)和\(a_{i+1}\)连边后，\([i,j]\)是连续段当且仅当\([i,j]\)是一个联通块。

是联通块则点数-边数=1。

由于每次询问右端点单调不减，所以可以对于每条边\(u,v(u\lt v)\)，当询问右端点\(\geq v\)的时候，左端点\(\leq u\)的区间边数+1。

那么就变成区间加，区间询问最小值和最小值出现的编号最大的位置。

时间复杂度单次\(O(\log n)\)，于是总复杂度\(O(n\log n)\)