【模板】普通平衡树&【模板】普通平衡树（数据加强版）
考虑最简单的平衡树——Treap（Tree+heap），从它的名字上就可以看出它是树和堆结合的产物。
那它究竟是怎么样呢？别着急，要研究它，必须研究它的基础版本——Binary Search Tree，二叉搜索树，简称BST。
简单来说，它需要满足对于任意一点，它的左子树内的任意点的点权均小于它的权值，右子树内的任意点的点权均大于它的权值。（不考虑重复元素）
它的中序遍历点权升序。
对于插入一个值，可以在BST中根据权值大小向左/右子树进入，最后插入在叶子节点。
删除操作太麻烦，不说了。
最坏情况下会退化成一条链。
Treap
下面正式进入正题。
我们首先给出一棵已经建立的合法的Treap：
如图，key表示实际权值，priority表示随机的优先级。
顾名思义，Treap不仅要满足BST的性质（对于key），还有满足二叉堆的性质（对于priority）（使用大根堆或小根堆均可）。
每个节点存储6个信息：
- 左儿子
- 右儿子
- 键值
- 随即优先级
- 数量
- 子树大小
最后两个主要处理与排名相关的操作。
然后就是左旋和右旋。
不想说了，参考这篇题解算了：https://blog.csdn.net/yanweiqi1754989931/article/details/117755252
代码
强调实现时的注意事项：
mt19937生成的随机数为无符号整型- 插入、删除后记得上推更新
- 很多函数可以对称的写，如左旋/右旋，前驱/后继，
- 加强版
grank找到不存在的点需要返回1，因为有可能这个值是大于已插入的所有数的 - 左旋右旋随便画个图就能一目了然