Treap是一种弱平衡的二叉搜索树，它同时符合二叉搜索树和堆的性质：
二叉搜索树：右子节点值>父节点>左子节点
堆：子节点的优先值比父节点值小
我们让每个节点的值符合二叉搜索树的性质，同时给每个节点赋一个随机的优先值，让优先值满足堆的性质。
由于优先值是随机的，一旦不满足堆性质就会产生旋转，所以就很难出现退化成链的情况，达到平衡的效果。
Treap分为旋转Treap和无旋treap两种，旋转treap的旋转操作分为右旋和左旋：
写成代码如下：
void left_rotate(int& id) { //左旋
int tmp = rchild[id];
rchild[id] = lchild[tmp];
lchild[tmp] = id;
id = tmp;
push_up(lchild[id]);
push_up(id);
}
void right_rotate(int& id) { //右旋
int tmp = lchild[id];
lchild[id] = rchild[tmp];
rchild[tmp] = id;
id = tmp;
push_up(rchild[id]);
push_up(id);
}
旋转操作其实只涉及两个点，交换下孩子即可。
树的储存，使用数组模拟结构体：
int lchild[maxn];
int rchild[maxn];
int val[maxn],prio[maxn];
int siz[maxn], cnt[maxn];
int tot, root;
val存值，prio存节点的优先值，siz记录某节点的子节点的数量，cnt记录某节点的值出现的次数，用于处理重复元素的情况。
创建节点：
int create(int v) {
//创建节点，并给予随机优先值
tot++;
val[tot] = v;
prio[tot] = rand();
siz[tot] = 1;
cnt[tot] = 1;
return tot;
}
用rand函数给prio赋随机值。
更新siz的push_up操作：
void push_up(int id) {
//用于旋转后重新计算size
siz[id] = siz[lchild[id]] + siz[rchild[id]] + cnt[id];
}
在旋转/插入后siz可能会变化，要push_up从下到上更新。
初始化：
void build() { //初始化，插入一个正无穷和一个负无穷
root = create(-inf);
rchild[root] = create(inf);
push_up(root);
}
初始化要先往里边塞一个正无限和一个负无限节点。
插入：
在二叉查找树上找位置插入，找到树缺位或已有节点修改。每次插完都要检测符不符合堆的性质，如果不符合就用旋转的方式进行平衡。
注意，每层插入递归结束后都要进行一次push_up重新计算size值。
void insert(int& id, int v) {
if (!id) { //找到树缺位（引用指向的变量（l/rchild）为0）
id = create(v);
return;
}
if (v == val[id]) cnt[id]++;
else { //遍历查找树，知道找到他该在的位置
if (v < val[id]) {
insert(lchild[id], v);
//每次插完都要检测符不符合堆的性质，不符合就平衡
if (prio[id] < prio[lchild[id]]) right_rotate(id);
}
else {
insert(rchild[id], v);
if (prio[id] < prio[rchild[id]]) left_rotate(id);
}
}
push_up(id); //插入后size会变，沿路更新
}
