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
      
       #include
       
        #include
        
         #include
         
          #include
          
           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
           
            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\n",find(x)); if(id==4) printf("%d\n",findx(x)); if(id==5) {insert(x);printf("%d\n",key[getpre(roof)]);Delete(x);} if(id==6) { insert(x); printf("%d\n",key[getnext(roof)]); Delete(x); } }}