题意
写一棵平衡树，需要实现如下几种操作：
- 插入 \(x\) 数
- 删除 \(x\) 数(若有多个相同的数，因只删除一个)
- 查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 \(+1\) )
- 查询排名为 \(x\) 的数
- 求 \(x\) 的前驱(前驱定义为小于 \(x\)，且最大的数)
- 求 \(x\) 的后继(后继定义为大于 \(x\)，且最小的数)
思路
BST
什么是BST（二叉查找树）呢？
BST是一种二叉树，用于做一些查找操作（其实很多是题意中所说明的工作）。BST需要满足当前结点的左子树中所有结点的键值要小于当前结点，而右子树相反，所有结点的键值都要大于当前节点。
BST的性质：
- 一棵BST能对应一个键的集合
- 一个集合对应的BST不为一
- 对BST做中序遍历，得到的序列是严格单调递增的
Treap
Treap是一种编程比较简单的平衡树，它在普通二叉搜索树的基础上，给每个结点一个随机的优先级。树上每个结点在满足BST的性质以外，还需要根据优先级满足堆的性质。
旋转操作
为了要让Treap同时满足BST和堆的性质，肯定要对其结构进行调整。这个调整的方式被称为旋转。在Treap中，只有两种旋转操作——左旋和右旋
左旋一个子树，会把它的根挪到根的左子树部分，同时根的右子树成为子树的根，再把右子树的左子树接到根的右子树上。
右旋一个子树，会把它的根转到右子树上，同时根的左子树成为子树的根。在把左子树的右子树接到根的右子树上。
插入操作
- 如果当前没有结点，那么就到了位置，直接创建新的。
- 如果当前结点的键值为 \(x\),那么懒添加，在当前结点的出现次数记录那里直接 \(+1\) 即可。
- 否则根据BST性质接着遍历即可。
- 插入后如果不满足Trep的堆性质了，旋转。
删除操作
- 如果不存在，那么返回即可。
- 如果要删除的元素是在子树中，去子树里找
- 如果当前要删除结点是叶子，那么直接删除。
- 如果当前点只有一个孩子，那么直接把自己跟孩子换了就行。
- 否则有两个孩子的话旋转一下后直接删除。
查询x数的排名
- 如果当前节点是x，直接返回左子树大小 \(+1\) 即可。
- 否则接着安照BST性质遍历即可。
查询排名为x的数
- 与上一个操作很像，读者可以自行想想
前驱后继
读者也可以自行想想。
tips
我们为什么不直接用BST呢？可以想想，如果给出一个单调递增/递减的序列，是不是都一直往右子树/左子树上添加了。一个满二叉树（最好情况）的时间复杂度（层数）是 \(\log{n}\) 的，但是如果都往一个方向，那么层数就变成 \(n\) 了，这不好。但是如果旋转，每一次都能减少一层，然后随机化也会让这个序列达到一个相对平衡的状态。所谓的堆性质也可以理解为是一个“莫须有”的罪名罢了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
const ll INF=2147483647;
ll root;
struct Node{
ll son[2];//0为左孩子
ll cnt,value,pri,size;
//出现次数，值，优先级，个数
}t[MAXN];
void push_up(ll u){
t[u].size=t[t[u].son[0]].size+t[t[u].son[1]].size+t[u].cnt;
//为左子树的大小+右子树的大小+自身的个数
}
void rotate(ll &u,ll d){
//d=0为左旋，d=1为右旋
ll k=t[u].son[d^1];
t[u].son[d^1]=t[k].son[d];
t[k].son[d]=u;
push_up(u);
push_up(k);
u=k;
}
ll sz;
void insert(ll &u,ll x){
if(u==0){
u=++sz;//新元素
t[u].cnt=t[u].size=1;//叶子大小和元素个数都为1
t[u].value=x;//值为x
t[u].pri=rand();//随机赋优先级
return;
}
if(t[u].value==x) {
t[u].size++;//更改空间
t[u].cnt++;//多了一个一样的
return;
}
ll k=x>t[u].value;//在左子树还是右子树里
insert(t[u].son[k],x);
if(t[u].pri<t[t[u].son[k]].pri){//是否满足堆性质
rotate(u,k^1);//旋转，旋哪个子树
}
push_up(u);//更新
}
void del(ll &u,ll x){
if(u==0){
return;//压根不存在
}
if(x<t[u].value){
del(t[u].son[0],x);//在左子树里
}else if(x>t[u].value){
del(t[u].son[1],x);//在右子树里
}else{
if(t[u].cnt>1){
t[u].size--;//懒删除
t[u].cnt--;//同上
}else if(t[u].son[0]==0&&t[u].son[1]==0){
u=0;//叶子结点，直接删除就行了
}else if(t[u].son[0]!=0&&t[u].son[1]==0){
u=t[u].son[0];//接到左子树上
}else if(t[u].son[0]==0&&t[u].son[1]!=0){
u=t[u].son[1];//接到右子树上
}else{
ll k=t[t[u].son[0]].pri>t[t[u].son[1]].pri;//两边都有，选择删
rotate(u,k);//旋一下，把根换到底下
del(t[u].son[k],x);//接着删
}
}
push_up(u);//更新
}
ll x_rank(ll u,ll x){
if(u==0){
return 0;//不存在
}
if(t[u].value==x){
return t[t[u].son[0]].size+1;//小的元素个数再+1
}
if(x<t[u].value){
return x_rank(t[u].son[0],x);//比当前小，在左子树里
}
return t[t[u].son[0]].size+t[u].cnt+ x_rank(t[u].son[1],x);//左子树的大小+当前结点元素个数+右子树中的排名
}
ll rank_x(ll u,ll x){
if(t[t[u].son[0]].size>=x){
return rank_x(t[u].son[0],x);//左子树的排名比x大
}
if(t[t[u].son[0]].size+t[u].cnt<x){
return rank_x(t[u].son[1],x-t[t[u].son[0]].size-t[u].cnt);//这个结点的排名比x小，去右边，同时减掉当前排名
}
return t[u].value;//找到了，返回元素
}
ll pre(ll u,ll x){
if(u==0){
return -INF;//不存在前驱
}
if(t[u].value>=x){
return pre(t[u].son[0],x);//比x大，去左边
}
return max(t[u].value, pre(t[u].son[1],x));//是不是当前的，还是在右子树里，取max
}
ll suc(ll u,ll x){
if(u==0){
return INF;//不存在
}
if(t[u].value<=x){
return suc(t[u].son[1],x);//比x小，去右边
}
return min(t[u].value, suc(t[u].son[0],x));//选最小的，与前驱相同
}
int main(){
srand(time(NULL));
ll n;
scanf("%lld",&n);
for (int i = 1; i <=n ; ++i) {
ll op,x;
scanf("%lld%lld",&op,&x);
if(op==1){
insert(root,x);
}else if(op==2){
del(root,x);
}else if(op==3){
printf("%lld\n",x_rank(root,x));
}else if(op==4){
printf("%lld\n",rank_x(root,x));
}else if(op==5){
printf("%lld\n",pre(root,x));
}else{
printf("%lld\n",suc(root,x));
}
}
return 0;
}