更快的持久化文艺平衡树?!

· · 算法·理论

更快的持久化文艺平衡树?!

模板题 P5055 【模板】可持久化文艺平衡树

之前交过 WBLT 的代码,效果不怎么好(3.29s)。

最近在交普通文艺平衡树的 Leafy Tree 代码,跑的飞快(不过跑不过神秘 splay 和神秘算法)。

总所周知 Leafy Tree 维护文艺平衡树的时候,不维护平衡会变快,并且我不知道怎么卡。

后来想想,如果 Leafy Tree 在维护普通文艺平衡树的时候效果很好,但是为什么在可持久化文艺平衡树模板题里就效果不佳呢????

发现了!有插入和删除操作!

发现插入和删除操作我竟然是先 split 再 merge 的。。。

这样太劣了!

直接换成主席树状物的插入删除,

这就是 Leafy Tree 的优势!!Leafy 的形态使得很多操作都能直接在树上完成!

写了一发,2.79s。

经过了一些卡常,来到了 2.61s。