Codeforces 455D Scapegoat tree 解决动态的树套树问题

传送门

昨天CF的题。给一个数列,每次操作要么把一个区间的末尾数字插到头部,要么询问区间内等于某个给定值的数字的个数。
显然分块可以做,也有优雅的Splay方法,但是直观的树套树也是不错的。
一般正常是线段树套平衡树,这样复杂度很容易分析,但是对于第一维空间也是动态的情况,就没法处理了。
而平衡树套平衡树最大的问题就是旋转的时候结点内套的内容没法批量修改。
于是使用不太旋转的平衡树(比如 Scapegoat tree)就是很自然的想法了。
对于这题而言,第一维用Scapegoat tree,第二维用map就可以了。
但是写起来有一个要注意的点,因为Scapegoat tree不太好delete,我是采用lasy delete的方法。
而lasy delete以后忽略空节点的size不能用作判定平衡情况,因为被delete的元素很多的时候,这样判定树的平衡性就完全不对了。
于是不包含空节点的size和包含空节点的nodeCount都要记录。
不过跑出来的速度似乎和同样用hashmap的分块差不多,虽然理论上来讲这个时间复杂度是O(Q log^2 N),分块是 O(Q^{1.5} log N)的。

code

加入对话

3条评论

    1. 确实我觉得会慢,因为重构的时候,STL的unordered_map是hashmap,但是hashmap扩容的时候是很蛋疼的,虽然策略类似于vector,但在这种知道大小的情况下,显然还是有很大优化余地的。手写个hash估计会好很多。

留下评论

回复 wuyiqi 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注