题解 P5494【模板】线段树分裂

· · 题解

这里献上一份不算特别缓慢的平衡树题解。

因为标签里有提示平衡树和线段树，所以我们优先选择用平衡树维护这些集合。

钳制芝士：fhq-Treap

朴素做法及分析

对于一个集合，我们用一个可重 treap 进行维护。

对于操作 0，直接将 p 按 (-\infty,x),[x,y],(y,+\infty) 分裂成三块，新的集合就是中间那一块，把两边的合并起来就是 p 了。

（操作 1 最后分析）

对于操作 2，还是裂成三块，如果中间那块有的话，直接加 cnt 就可以了，否则的话就新建节点，最后再 merge 起来即可。

对于操作 3，一样裂成三块，输出中间那一块的大小就可以了。

对于操作 4，写一个平衡树上查第 k 小就可以了。

至此，所有的操作都是 treap 基本操作，可以保证复杂度为 O(n\log n)。

再来看操作 1，容易发现要合并的两个集合的值域是有可能会相交的，所以不能简单地 merge。

考虑线段树合并是如何做到的：线段树每次将所有值划分为两部分，然后分别合并。

那我们可以仿照线段树的做法，设要合并的两棵树的根节点为 x 和 y 那将 y 以 x 的权值裂成三块，然后分别递归合并。

然后我们天真地这样写了，然后交了上去。

剪切板代码1

并不能通过，倒数第二个点超时，如题面所述，倒数第二个点 hack 了平衡树。

这时候我们要发扬信息学精神（bushi），尝试看看到底是如何被卡的。

优化

下载了数据后我们可以发现，所有操作就是从集合 1 中截一段下来，插入一个数，再接回去。

所以就容易发现了，这种做法缺陷在于在操作 1 的合并中没有办法合理地改变树地形态，导致高度会不断地累积，无法得到调整。这一点可以记录一下树高然后跑一下得到验证：树高很快就增长到了三四千。

我们首先可以加入一个十分浅显的优化：如果两棵树值域已经不交了，那么直接 merge 就可以了。可以发现，这样跑起来会快很多了，但是依然要跑一分钟左右。（因为复杂度并没有实质性的改变）

我们看到每次总是 y 往 x 上合并，很容易发生大的并到小的上的情况，这时树的高度就会增加，所以这启发了我们可以采用启发式合并。

我们每次合并时都将小的往大的上合并，这时可以惊喜的发现开 O2 本地只用跑 800ms 左右，然后一提交，就通过了。

剪切板代码2

提交记录

简单分析一下复杂度：从树高的角度来说，每次将小的插进大的是不会对大树的树高产生影响的，所以每次合并后树高都会保持原高度，从而避免了原来结构不变带来的高度猛增。同样这一点可以运行代码输出树高得到验证。

因此这个合并操作复杂度外层是类似于线段树的，每个点会贡献 O(\log n) 层的递归，而每层递归都需要对小树进行一次 split，因而复杂度为 O(\log^2n)。

从数据结构稳定性的角度分析，实际上线段树就是凭自身结构做到了树高保持为 O(\log n) 的同时，还能够 O(1) 地分裂值域区间，而平衡树则需要通过启发式合并维护树高以及 split 分裂值域。

综合起来看，复杂度就是 O(n\log^2 n)。

由于每次 split 都发生在小树上，所以实际上第二个 log 是很跑不满的，这也就是为什么 O(n\log^2n) 也跑得比较快的原因。

虽然时间复杂度相比起来很拉，但是空间复杂度是 O(n)。大概算是一个优势吧。（笑）

（但是似乎这个 treap 的可拓展性更强一些）