Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
Hint
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
第二道splay模板题，调了我一个晚上，我再也不想看这题一眼，题解请看：http://blog.csdn.net/clove_unique/article/details/50630280
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> const int MAXN=100100; using namespace std; int tr[MAXN][2],cnt[MAXN],key[MAXN],size[MAXN],pr[MAXN]; int roof=0,tot=0; int n; void cl(){ memset(tr,0,sizeof(tr)); memset(cnt,0,sizeof(cnt)); memset(key,0,sizeof(key)); memset(size,0,sizeof(size)); memset(pr,0,sizeof(pr)); } int getx(int x) { return tr[pr[x]][1] == x; } void clar(int x){ tr[x][0]=tr[x][1]=pr[x]=key[x]=size[x]=cnt[x]=0; } void update(int now){ size[now]=cnt[now]; if(tr[now][0]) size[now]+=size[tr[now][0]]; if(tr[now][1]) size[now]+=size[tr[now][1]]; } void Rotate(int x,int kind){ int y=pr[x]; tr[y][!kind]=tr[x][kind]; pr[tr[x][kind]]=y; if(pr[y]) tr[pr[y]][tr[pr[y]][1]==y]=x; pr[x]=pr[y]; tr[x][kind]=y; pr[y]=x; update(y); update(x); } void splay(int x,int goal){ while(pr[x]!=goal){ if(pr[pr[x]]==goal){ Rotate(x,tr[pr[x]][0]==x); } else{ int y=pr[x],kind=tr[pr[y]][0]==y; if(tr[y][kind]==x){ Rotate(x,!kind); Rotate(x,kind); } else{ Rotate(y,kind); Rotate(x,kind); } } } if(goal==0) roof=x; } void insert(int k) { if(roof==0) {tot++,tr[tot][0]=tr[tot][1]=pr[tot]=0; roof=tot;size[tot]=cnt[tot]=1;key[tot]=k;return;} int now=roof,fa=0; while(1) { if(k==key[now]) { cnt[now]++;update(now),update(fa); splay(now,0);return; } fa=now; now=tr[now][ k > key[now]]; if(now==0) { tot++; tr[tot][0]=tr[tot][1]=0; pr[tot]=fa; size[tot]=cnt[tot]=1; tr[fa][k > key[fa]]=tot; key[tot]=k; update(fa); splay(tot,0); return; } } } int find(int zhi){ int ans=0,now=roof; while(1){ if(zhi<key[now]) now=tr[now][0]; else{ if(tr[now][0]) ans+=size[tr[now][0]]; if(key[now]==zhi){splay(now,0);return ans+1;} ans+=cnt[now]; now=tr[now][1]; } } } int findx(int rk){ int now=roof; while(1){ if(tr[now][0]&&rk<=size[tr[now][0]]) now=tr[now][0]; else{ int tmp=0; if(tr[now][0]) tmp+=size[tr[now][0]]; tmp+=cnt[now]; if(rk<=tmp) return key[now]; now=tr[now][1]; rk-=tmp; } } } int getpre(int x){ int now=tr[x][0]; while(tr[now][1]) now=tr[now][1]; return now; } int getnext(int x){ int now=tr[x][1]; while(tr[now][0]) now=tr[now][0]; return now; } void Delete(int x){ find(x); if(cnt[roof]>1) {cnt[roof]--;update(roof);return;} if(!tr[roof][0]&&!tr[roof][1]) {clar(roof);roof=0;return;} if(!tr[roof][0]){ int oldroof=roof; roof=tr[roof][1]; pr[roof]=0; clar(oldroof); return; } if(!tr[roof][1]){ int oldroof=roof; roof=tr[roof][0]; pr[roof]=0; clar(oldroof); return; } int oldrf=roof; int lf=getpre(roof); splay(lf,0); pr[tr[oldrf][1]]=roof; tr[roof][1]=tr[oldrf][1]; clar(oldrf); update(roof); return; } int main(){ cl(); scanf("%d",&n); for(int i=1;i<=n;i++){ int id,x;scanf("%d%d",&id,&x); if(id==1) insert(x); if(id==2) Delete(x); if(id==3) printf("%d ",find(x)); if(id==4) printf("%d ",findx(x)); if(id==5) {insert(x);printf("%d ",key[getpre(roof)]);Delete(x);} if(id==6) { insert(x); printf("%d ",key[getnext(roof)]); Delete(x); } } }