题目描述 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入xx数 删除xx数(若有多个相同的数，因只删除一个) 查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名) 查询排名为xx的数 求xx的前驱(前驱定义为小于xx，且最大的数) 求xx的后继(后继定义为大于xx，且最小的数) 输入格式 第一行为nn，表示操作的个数,下面nn行每行有两个数optopt和xx，optopt表示操作的序号( 1 \leq opt \leq 6 1≤opt≤6 )
输出格式 对于操作3,4,5,63,4,5,6每行输出一个数，表示对应答案
输入输出样例 输入 #1 复制 10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598 输出 #1 复制 106465 84185 492737 说明/提示 时空限制：1000ms,128M
1.n的数据范围： n \leq 100000 n≤100000
2.每个数的数据范围： [-{10}^7, {10}^7][−10 7 ,10 7 ]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢 这两个博客很好， https://blog.csdn.net/qq_30974369/article/details/77587168#commentBox https://tiger0132.blog.luogu.org/slay-notes 我把我的想法都写在注释里了，主要是供自己参考。
#include <bits/stdc++.h> using namespace std; const int N = 200005; int ch[N][2]; int par[N];//par[x],记录x的父结点 int val[N]; int cnt[N];//cnt[x]代表 x 存储的重复权值的个数。 int size[N];//size[x]代表 xx子树下的储存的权值数（包括重复权值） int ncnt;//方便位置的处理 int root;//记录根结点 bool chk(int x){//判断是否为右孩子，为右孩子为1 return ch[par[x]][1] == x; } void pushup(int x){//统计包括x以及以下的所有权值数(包括重复) size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x]; } void rotate(int x) {//将x与它的父结点进行互换 ,基本操作 int y = par[x],z = par[y],k = chk(x),w = ch[x][k^1]; ch[y][k] = w;par[w] = y; ch[z][chk(y)] = x;par[x] = z; ch[x][k^1] = y;par[y] = x; pushup(x);pushup(y); return; } void splay(int x, int goal = 0){//将x的父结点变成goal while(par[x] != goal){ int y = par[x],z = par[y]; if(z != goal){//z不到根结点 if(chk(x) == chk(y)) rotate(y);//如果方向相同，则先旋转y else rotate(x);//如果不同，则先旋转x } rotate(x);//但是x无论如何都要旋转一下 } if(!goal) root = x;//如果goal为0,说明此时x为根结点，所以将根结点中换掉 } void insert(int x) { int cur = root,p = 0;//cur为当前结点,p为当前结点的父结点 while(cur && val[cur] != x){ p = cur;//将父结点记录下来 cur = ch[cur][x > val[cur]];//查找需要插入的位置 } if(cur){//如果当前cur非0，就说明这个结点是有的 //那么直接重复的权+1就好了 cnt[cur]++; }else {//此时没有x这个结点，就需要新建一个结点， cur = ++ncnt;//首先需要新建这个点在哪个位置 if(p){//p如果是非0的话,就不是在根结点的位置的建立 ch[p][x > val[p]] = cur; } ch[cur][0] = ch[cur][1] = 0;//指向的两个分叉分别分别为0 cnt[cur] = size[cur] = 1;//眼前情况下只有一个 val[cur] = x;//这个位置的值是多少 par[cur] = p;//记录下cur的父亲结点 } splay(cur);//进行伸展 } void find(int x){//需要查找x这个值 int cur = root;//从根结点开始查找 while(ch[cur][x > val[cur]]&& x != val[cur]){//保证要查找的位置不为0并且 X!=val[cur] cur = ch[cur][x > val[cur]];//不停的递归 } splay(cur);//进行伸展 return; } int kth(int k) {//查找第k大 int cur = root; while(true){ if(ch[cur][0] && k <= size[ch[cur][0]]){//k如果<=左子树以及下面的个数的和，说明在左侧 cur = ch[cur][0]; }else if(k > size[ch[cur][0]]+cnt[cur]){//如果k>左子树下面的个数+当前结点的个数的和,说明在右侧 k -= size[ch[cur][0]]+cnt[cur];//结点的个数需要减掉 cur = ch[cur][1];//指向右子树 }else {//左子树下面的个数+当前结点的个数 == k,说明已经找到了 splay(cur);//伸展 return cur; } } } int pre(int x) {//前驱，用来查找比x小的最大的值 find(x);//将当前x移到根结点 if(val[root] < x) return root;//如果当前根结点的值小于x，直接返回根结点 int cur = ch[root][0];//因为需要比x小，所以肯定在左边 while(ch[cur][1]){//要反着找最大值 cur = ch[cur][1]; } return cur; } int succ(int x) {//后继，用业查找比x大的最小的值 find(x);//将当前x移到根结点 if(val[root] > x) return root;//如果当前根结点的值大于x，直接返回根结点 int cur = ch[root][1];//因为需要比x大，所以肯定在右边找 while(ch[cur][0]){//要反着找最小的 cur = ch[cur][0]; } return cur; } void remove(int x) { //删除x int last = pre(x);//找到前驱 int next = succ(x);//找到后继 splay(last,0);//将前驱变成根结点 splay(next,last);//将next的父结点改成last //此时next是last的右孩子,x是next的左孩子 int del = ch[next][0];//记录next的左孩子 if(cnt[del] > 1){//大于1直接个数减1 cnt[del]--; splay(del,0);//进行伸展 }else { ch[next][0] = 0;//直接删除这个点 } pushup(next); pushup(last); } int n, op, x; int main() { scanf("%d", &n); insert(0x3f3f3f3f); insert(0xcfcfcfcf); while (n--) { scanf("%d%d", &op, &x); switch (op) { case 1: insert(x); break; case 2: remove(x); break; case 3: find(x); printf("%d\n", size[ch[root][0]]); break; case 4: printf("%d\n", val[kth(x+1)]); break; case 5: printf("%d\n", val[pre(x)]); break; case 6: printf("%d\n", val[succ(x)]); break; } } }