fzsplay

· · 个人记录

由于 Splay 有时候没那么优秀,我们现在来优化一下它。

提到了 Splay,自然会想到它的 splay 操作,考虑 Splay 操作是在干什么,我们注意到它是在把一个节点旋转的根,这启发我们用 LCT 的 makeroot 操作来维护它,于是我们想到:用 LCT 维护 Splay 。

所以,我们直接用 LCT 的各个操作来维护 Splay,发现只要把LCT维护的动态树换成Splay即可,于是我们发明出来了一个绝妙的算法:fzsplay

类似fzxds,因为LCT是用Splay维护的,所以LCT内部的Splay可以用LCT来维护,这样就可以实现 fzsplay^2,fzsplay^3,...,fzsplay^{+ \infin},于是时间复杂度优化到了 O(n \log^{+\infin} n)