您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入数值 xx。
- 删除数值 xx(若有多个相同的数，应只删除一个)。
- 查询数值 xx 的排名(若有多个相同的数，应输出最小的排名)。
- 查询排名为 xx 的数值。
- 求数值 xx 的前驱(前驱定义为小于 xx 的最大的数)。
- 求数值 xx 的后继(后继定义为大于 xx 的最小的数)。
注意： 数据保证查询的结果一定存在。
输入格式
第一行为 nn，表示操作的个数。
接下来 nn 行每行有两个数 optopt 和 xx，optopt 表示操作的序号(1≤opt≤61≤opt≤6)。
输出格式
对于操作 3,4,5,63,4,5,6 每行输出一个数，表示对应答案。
数据范围
1≤n≤1000001≤n≤100000,所有数均在 −107−107 到 107107 内。
输入样例：
8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1输出样例：
2 20 20 20
核心思路：首先我们需要知道的就是Treap=BST+heap,然后我们想一下为什么需要这么维护呢。这个其实和我们设置的节点的信息有关系，我们的节点信息中有key(储存的是节点的值),val(储存的是一个随即编号).然后我们再想为什么还需要一个val呢，因为我们的BST会因为给定我们数组的逆序对越少而退化成链式结构，也就是不在是我们的树形结构了。不如数组:1 2 3 4 5 6,这样的话我们的BST就只会有右子树，也就是一条链。所以我们的val主要就是打乱下顺序，使得重新变为树.
要注意的是我们的heap主要是操作val中的值，也就是需要我们根节点的val需要严格大于他的子节点。因为我们这里的堆是一个大根堆。
下面看一个小根堆的示意图：(大根堆就是我们的那个堆的权值相反就好了)
其实我们这么做的目的就是为了让我们的二叉搜索树变胖。下面还普及一个二叉搜索树的重要推导：其实我们的二叉搜索树的一个最终结果就是采用中序遍历，其实我们也还可以把这些节点投影下来理解，这样更加的直观和方便。我们可以以上面那个图为例，投影下来就是：1 3 4 5 2 6 7，这个和我们中序遍历的结果是一样的。
然后理解了基本的含义之后，接下来就是我们的旋转操作。一定要注意的是我们的旋转操作是在保持平衡树的前提下，来维护我们的堆的性质，比如我们的是大根堆那我们就需要把那些小的节点放到下面的那一层上面去
首先先从定义出发：
- 在不影响搜索树的性质的前提下，把旋转相反的节点变为根节点(看下下面的图就理解了)
- 不影响性质，并且在旋转过后，跟旋转方向相同的子节点变来了原来的根节点.
可以通过看图理解：
还有几个就是基本的一些操作了，比如增删查改，一定要注意我们我们只要查的时候是不需要对节点开引用的，其他都是需要的。因为那个节点之后的节点都是需要改变的。还有个注意的点是我们的节点是从1号点开始的，所以0号节点是空的
下面的细节都在代码里面：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int INF = 1e8;
const int N = 1e6 + 10, S = 55, M = 10000010;
int n, root, idx;
struct Node {
int l, r;
int cnt;//因为一个一棵树里面可能包含多个相同的数
int size;//表示的是子树的大小
int val;//也就是我们随机分配的堆的编号
int k;//这个就是我们编号所对应的值
}tr[N];
void pushup(int p)
{
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;//这里还是比较好理解的，和线段树的差不多更新下size，唯一需要注意的就是tr[p].cnt,不要忘记了这些重复的节点
}
int new_node(int k)
{
tr[++idx].k = k;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;//因为加入的这个点一定是一个叶子节点
return idx;
}
void zig(int& u)//右旋
{
int q = tr[u].l;
tr[u].l = tr[q].r;
tr[q].r = u;//注意这里不是tr[u].l=u;
u = q;//因为现在q是根节点了
pushup(tr[u].r);//把现在的右子树的一个大小更新一下，其实我们通过图可以发现其实影响的也就是这个新的根和其对应的右子树的大小.
pushup(u);//可以仔细看下那个旋转的图的2号的左右子树的变化
}
void zag(int& u)//左旋也就是和上面那个相反
{
int q = tr[u].r;
tr[u].r = tr[q].l;
tr[q].l = u;//这个地方需要注意，不是tr[u].r=u;
u = q;
pushup(tr[u].l);
pushup(u);
}
void build()//建树操作，为了正确性增加两个哨兵：正无穷和负无穷
{
new_node(-INF), new_node(INF);
root = 1;
tr[1].r = 2;
pushup(root);
if (tr[1].val < tr[2].val)//因为第二个节点是正无穷所以在右边，所以需要左旋.
zag(root);
}
void insert(int& u, int k)
{
if (u == 0)
u = new_node(k);//如果是空了。那么就新建
else
{
if (tr[u].k == k)//这里表示的是找到了相同的节点
{
tr[u].cnt++;
}
else
{
if (tr[u].k > k)
{
insert(tr[u].l, k);
if (tr[tr[u].l].val > tr[u].val)//不平衡就需要立马调整
{
zig(u);
}
}
else
{
insert(tr[u].r, k);
if (tr[tr[u].r].val < tr[u].val)
zag(u);
}
}
}
pushup(u);//最后一定要记得更新
}
void del(int& u, int k)
{
if (u == 0)//说明没有找到这个节点
return;
if (tr[u].k == k)//找到了
{
if (tr[u].cnt > 1)
tr[u].cnt--;
else
{
if (tr[u].l || tr[u].r)//表示如果不是叶子节点的话
{
if (!tr[u].r || tr[tr[u].l].val > tr[tr[u].r].val)
{//如果r子树是空的或者右子树不为空但是左子树的val大于右子树那我们同样可以右旋
zig(u);
del(tr[u].r, k);//一定不要忘记我们最终的目的，我们是通过不断地递归右旋，是这个节点转变为叶子节点从而删除.
}
else
{
zag(u);
del(tr[u].l, k);
}
}
else
u = 0;//如果是叶子节点就不要考虑平衡了，直接删除
}
}
else if (tr[u].k > k)//如果没有找到那就递归到左右子树去寻找
del(tr[u].l, k);
else del(tr[u].r, k);
pushup(u);//上传更新
}
int get_rank(int u, int k)
{
if (u == 0)
return 0;//空节点随便返回
if (tr[u].k == k)//相等的排名，我们就需要算下左子树的大小就好了.
{
return tr[tr[u].l].size + 1;
}
if (tr[u].k > k)
{
return get_rank(tr[u].l, k);//大了就往左边找
}
return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, k);//如果左子树的还没有满足条件的，那就往右边.
}
// int get_key(int u, int rank)//找下下面的代码和我注释掉的代码的差异
// {
// if(u == 0) return INF;
// if(tr[tr[u].l].size >= rank) return get_key(tr[u].l, rank);//找左边
// if(tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].k;//如果满足条件就直接return
// return get_key(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);//不然就找右边
// }
int get_key(int u, int rank)//根据排名找对应的值
{
if (u == 0)//表示节点是空的
return INF;
if (tr[tr[u].l].size >= rank)//左边的比这个大了
return get_key(tr[u].l, rank);//一定要注意return
if (tr[tr[u].l].size + tr[u].cnt >= rank)//一定还要注意我们还有cnt
{
return tr[u].k;
}
return get_key(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);//往右子树找一定要注意需要减去我们左边 已经找到的排名
}
int get_pr(int u, int k)//前驱,首先我们需要需要知道前驱是个什么东西，他是第一个小于k的数
{
if (u == 0)
return -INF;
if (tr[u].k >= k)
{
return get_pr(tr[u].l, k);//如果大于这个数，我们就去左子树
}
return max(get_pr(tr[u].r, k), tr[u].k);//如果小于，就去右子树。一定要注意取max，也就是当前的和右子树的中的数
}
int get_ne(int u, int k)//后继：第一个大于k的数,做法是和前驱相反的
{
if (u == 0)
return INF;
if (tr[u].k <= k)
return get_ne(tr[u].r, k);
return min(get_ne(tr[u].l, k), tr[u].k);//这里是小于并且还需要注意我们的递归函数是放在了第一个参数
}
int main()
{
build();
cin >> n;
while (n--)
{
int op, x;
cin >> op >> x;
if (op == 1)
insert(root, x);
else if (op == 2)
del(root, x);
else if (op == 3)
cout << get_rank(root, x) - 1 << endl;//要注意我们插入了一个哨兵所以需要减一
else if (op == 4)
cout << get_key(root, x + 1) << endl;//这里的加1也是一个原理，需要跳过哨兵
else if (op == 5)
cout << get_pr(root, x) << endl;
else
cout << get_ne(root, x) << endl;
}
return 0;
}