您需要写一种数据结构，来维护一些数，其中需要提供以下操作：
1. 插入x
2. 删除x(若有多个相同的数，因只删除一个)
3. 查询x的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
1.n的数据范围：$n<=100000$
2.每个数的数据范围：$[-2e9,2e9]$
题解:
二叉搜索树可以完成目标,但是单次操作的时间复杂度可能退化为线性
因此使用平衡二叉树,$treap$(树堆)
树堆是各类平衡树中,速度和代码复杂度比较均衡的一个
速度比splay快且好写,比sbt,替罪羊慢但简单,个人觉得代码比较简单
BZOJ
LOJ
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
int casn,n,m,k;
#define nd treap[now]
#define ndl treap[treap[now].l]
#define ndr treap[treap[now].r]
#define ndt treap[tmp]
struct node {
int l,r,val,num,size,rnd;
}treap[maxn];
int cnt,root,ans;
inline void resize(int now){
nd.size=ndl.size+ndr.size+nd.num;
}
inline void rturn(int &now){
int tmp=nd.l;
nd.l=ndt.r,ndt.r=now;
ndt.size=nd.size;
resize(now);
now=tmp;
}
inline void lturn(int &now){
int tmp=nd.r;
nd.r=ndt.l,ndt.l=now;
ndt.size=nd.size;
resize(now);
now=tmp;
}
void insert(int &now,int val){
if(!now) {
now=++cnt;
nd=(node){0,0,val,1,1,rand()};
return ;
}
nd.size++;
if(val==nd.val)nd.num++;
else if(val>nd.val){
insert(nd.r,val);
if(ndr.rnd<nd.rnd) lturn(now);
}else{
insert(nd.l,val);
if(ndl.rnd<nd.rnd) rturn(now);
}
}
void erase(int &now,int val){
if(!now) return ;
if(val==nd.val){
if(nd.num>1){
nd.num--,nd.size--;
return ;
}
if(nd.r*nd.l==0) now=nd.l+nd.r;
else {
if(ndl.rnd<ndr.rnd) rturn(now);
else lturn(now);
erase(now,val);
}
}else {
nd.size--;
if(val>nd.val) erase(nd.r,val);
else erase(nd.l,val);
}
}
int query_rank(int now,int val){
if(!now) return 0;
if(val==nd.val)return ndl.size+1;
if(val>nd.val) return ndl.size+nd.num+query_rank(nd.r,val);
return query_rank(nd.l,val);
}
int query_val(int now,int rank){
if(!now) return 0;
if(rank<=ndl.size) return query_val(nd.l,rank);
if(rank-ndl.size<=nd.num) return nd.val;
return query_val(nd.r,rank-ndl.size-nd.num);
}
int query_pre(int now,int val){
if(!now) return ans;
if(val<=nd.val) return query_pre(nd.l,val);
ans=nd.val;
return query_pre(nd.r,val);
}
int query_sub(int now,int val){
if(!now) return ans;
if(val>=nd.val) return query_sub(nd.r,val);
ans=nd.val;
return query_sub(nd.l,val);
}
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
int root=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a==1) insert(root,b);
if(a==2) erase(root,b);
if(a==3) printf("%d\n",query_rank(root,b));
if(a==4) printf("%d\n",query_val(root,b));
if(a==5) printf("%d\n",query_pre(root,b));
if(a==6) printf("%d\n",query_sub(root,b));
}
#ifdef test
fclose(stdin);fclose(stdout);system("out.txt");
#endif
return 0;
}