专栏文章

fzsplay

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqynkhs
此快照首次捕获于
2025/12/04 12:53
3 个月前
此快照最后确认于
2025/12/04 12:53
3 个月前
查看原文
由于 Splay 有时候没那么优秀,我们现在来优化一下它。
提到了 Splay,自然会想到它的 splay 操作,考虑 Splay 操作是在干什么,我们注意到它是在把一个节点旋转的根,这启发我们用 LCT 的 makeroot 操作来维护它,于是我们想到:用 LCT 维护 Splay 。
所以,我们直接用 LCT 的各个操作来维护 Splay,发现只要把LCT维护的动态树换成Splay即可,于是我们发明出来了一个绝妙的算法:fzsplay
类似fzxds,因为LCT是用Splay维护的,所以LCT内部的Splay可以用LCT来维护,这样就可以实现 fzsplay2,fzsplay3,...,fzsplay+fzsplay^2,fzsplay^3,...,fzsplay^{+ \infin},于是时间复杂度优化到了 O(nlog+n)O(n \log^{+\infin} n)

评论

0 条评论,欢迎与作者交流。

正在加载评论...