Splay 的 Finger-Search 优化启发式合并

众所周知，平衡树的启发式合并是 \(O(n\log^2 n)\) 的。

证明：每个点最多被重新取出并插入 \(\log n\) 次（每次操作后连通块大小至少增加一倍），插入复杂度是 \(O(\log n)\) 的，所以总时间复杂度 \(O(n\log^2 n)\)。

但是使用 \(\text{Splay}\)，我们可以做到 \(O(n\log n)\) 的启发式合并。

合并时，将点的个数较小的平衡树中的元素按升序/降序依次插入到大的平衡树中即可。

不会证时间复杂度

感性理解一下：每次插入操作后被插入的节点会被旋转到根，此时再插入的话是从这个点开始寻找，若按升序/降序插入，总查找次数会小很多。

理性的证明我懒的看

相对线段树合并的优势：空间复杂度与值域无关

劣势：不好写，有一些维护复杂信息的题不能用