Top Tree 入门题,久闻大名!今天来挑战(自虐)一下。虽说是 Top Tree 入门题,但是网上大部分代码都是用 AAAT(参见某集训队论文,这个称呼甚至真的只是占位符而不是发明人名字缩写),也就是 Splay 维护虚子树信息的三叉动态树,其实我们之前也是遇到过三叉动态树的,比如:
不过这几个题都不涉及子树修改,所以只需要 access() 的时候顺手维护虚子树的状态即可逃课,而这个题里我们终于不得不直面灾厄了 …
和一般的三叉动态树里我们遇到的状况一样,最难的就是把 access() 过程里的虚实切换讨论清楚。
首先看图。我们增加辅助节点,来维护虚子树组成的 leafy tree,
leafy tree
添加辅助节点的想法,则类似于边分治里面我们强行弄成完全二叉树,不过这里和线段树那种 leafy tree 不同,我们可以直接用 Splay 来维护,因此插入一个新节点非常容易写,然后 …
搜了一圈,感觉 jerry3128 的这篇文章 写的最好,甚至给了四种方法的对比,基本上除了常数部分的复杂度分析都讲得特别清楚了 Orz。