Treap

UPD 02.15：更新了区间操作部分。

约莫半月前练习专题时，发现几道解法多样的题目，其中需要运用一些中高级数据结构。苦于之前没有学习过平衡树，便挑选了一种易于上手、实现简单的平衡树学习，也即FHQ Treap。由11年国家队队员范浩强发明。

为书写方便，文章中可能将直接使用$p$代指某节点的随机权值，$\text{val}$代指节点关键码（即记录的数值），$h$代指树高，$\text{siz}$代指子树大小，$\text{cnt}$代指节点副本数（相同关键码的节点），$\text{rt}$存储根节点编号。

（更多…）