treap怎样跑得更快

点开陈立杰13年的集训队论文，发现treap具有性质：每次新插入元素在treap中的子树大小为 $O(\log{n})$。 如果使用非旋treap作为名次树，insert/delete的时候可以在原树上走到需要插入的位置，再从这里开始merge/split，merge/split部分的期望复杂度为 $O(\log{\log{n}})$（其实鉴于对数函数的凹凸性问题，$E(\log{x})$ 和 $\log{E(x)}$ 并不能画等号，这里冷静一下是可以分析到 $O(1)$ 的），而 $O(\log{n})$ 部分的常数主要是在树上遍历，是静态操作，常数很小。 然而一般不会使用平衡树仅仅作为名次树。 ~~论treap的正确使用姿势~~