题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入xx数
- 删除xx数(若有多个相同的数，因只删除一个)
- 查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)
- 查询排名为xx的数
- 求xx的前驱(前驱定义为小于xx，且最大的数)
- 求xx的后继(后继定义为大于xx，且最小的数)
输入格式
第一行为nn，表示操作的个数,下面nn行每行有两个数optopt和xx，optopt表示操作的序号( 1 \leq opt \leq 61≤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 100000n≤100000
2.每个数的数据范围： [-{10}^7, {10}^7][?107,107]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
FHQTreap实现平衡树的模板题
具体解释：https://www.luogu.org/blog/Chanis/fhq-treap
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>#define MAXN 500001using namespace std;inline int read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n,m,op,a;
struct FHQTreap
{int ch[MAXN][3];//0 左孩子，1右孩子int val[MAXN];//每个点的权值int fix[MAXN];//每个点的随机权值int size[MAXN];//以每个点为根的树的大小int cnt,x,y,z,root;//cnt节点个数，x,y,z是临时的三棵树，root根树inline void update(int x){size[x]=1+size[ch[x][0]]+size[ch[x][1]];}inline int new_node(int x){size[++cnt]=1;val[cnt]=x;fix[cnt]=rand();return cnt;}int merge(int A,int B){if(!A||!B)return A+B;if(fix[A]<fix[B]){ch[A][1]=merge(ch[A][1],B);update(A);return A;}else{ch[B][0]=merge(A,ch[B][0]);update(B);return B;}}void split(int now,int k,int &x,int &y){if(!now)x=y=0;else{if(val[now]<=k)x=now,split(ch[now][1],k,ch[now][1],y);elsey=now,split(ch[now][0],k,x,ch[now][0]);update(now);}}//k小值int kth(int now,int k){while(1){if(k<=size[ch[now][0]])now=ch[now][0];else if(k==size[ch[now][0]]+1)return now;elsek-=size[ch[now][0]]+1,now=ch[now][1];}}//单点插入void add(int a){split(root,a,x,y);root=merge(merge(x,new_node(a)),y);}//删除(若有多个相同的数，因只删除一个）void del(int a){split(root,a,x,z);split(x,a-1,x,y);y=merge(ch[y][0],ch[y][1]);root=merge(merge(x,y),z);}//查询x数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)//并输出int findRank(int a){split(root,a-1,x,y);int res=size[x]+1;root=merge(x,y);return res;}//查询排名为a的数 ，a小值int findRankNum(int a){return val[kth(root,a)];}//输出a的前驱(前驱定义为小于a，且最大的数)int pre(int a){split(root,a-1,x,y);int res=val[kth(x,size[x])];root=merge(x,y);return res;}//输出a的后继(后继定义为大于a，且最小的数)int nxt(int a){split(root,a,x,y);int res=val[kth(y,1)];root=merge(x,y);return res;}} fhqTreap;int main()
{srand((unsigned)time(NULL));int T;T=read();while(T--){op=read();a=read();if(op==1){fhqTreap.add(a);}else if(op==2){fhqTreap.del(a);}else if(op==3){printf("%d\n",fhqTreap.findRank(a));}else if(op==4)printf("%d\n",fhqTreap.findRankNum(a));else if(op==5){printf("%d\n",fhqTreap.pre(a));}else{printf("%d\n",fhqTreap.nxt(a));}}return 0;
}