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]

 

Source

 Splay模板题，膜了YveH爷的模板，不过代码好长，常数还很大。。。好歹是打粗来了

1 #include 
       
          2 using namespace std;  3 struct SplayNode  4 {  5     SplayNode *fa,*ch[2];  6     SplayNode();  7     int data,num,size;  8     int chr() {
     return this==fa->ch[1];}  9     void updata() { size=ch[0]->size+ch[1]->size+num;} 10 }*null; 11 SplayNode::SplayNode() {fa=ch[0]=ch[1]=null; size=0; num=1;} 12 int n; 13 namespace Splay 14 { 15     SplayNode *Root; 16     void MakeTree() 17     { 18         null=new SplayNode; 19         *null=SplayNode(); 20         Root=null; 21     } 22     void rotate(SplayNode *x) 23     { 24         SplayNode *r=x->fa; 25         if (r==null || x==null) return; 26         int t=x->chr(); 27         r->ch[t]=x->ch[t^1]; 28         r->ch[t]->fa=r; 29         if (r->fa==null) Root=x; 30         else r->fa->ch[r->chr()]=x; 31         x->fa=r->fa; 32         x->ch[t^1]=r; 33         r->fa=x; 34         r->updata(); 35         x->updata(); 36     } 37     void splay(SplayNode *x,SplayNode *y) 38     { 39         for (;x->fa!=y;rotate(x)) 40             if (x->fa->fa!=y) 41                 if (x->chr()==x->fa->chr()) rotate(x->fa); 42                 else rotate(x); 43     }  44     void insert(int v) 45     { 46         SplayNode *r=Root; 47         if (Root==null) 48         { 49             Root=new SplayNode; 50             Root->data=v; 51             Root->updata(); 52             return; 53         } 54         if (Root->data==v) 55         { 56             Root->num++; 57             Root->updata(); 58             return; 59         } 60         while (r->ch[r->data
        
         ch[r->data
         
          data==v) 64             { 65                 r->num++; 66                 splay(r,null); 67                 return; 68             } 69         } 70         r->ch[r->data
          
           ch[r->data
           
            data=v; 72         r->ch[r->data
            
             fa=r; 73 splay(r->ch[r->data
             
              ch[0]->size) r=r->ch[0]; 81 else if (k>=r->ch[0]->size+1 && k<=r->ch[0]->size+r->num) return r; 82 else 83 { 84 k=k-r->ch[0]->size-r->num; 85 r=r->ch[1]; 86 } 87 } 88 return r; 89 } 90 SplayNode *find(int v) 91 { 92 SplayNode *r=Root; 93 while (r!=null) 94 { 95 if (r->data==v) 96 { 97 splay(r,null); 98 return r; 99 }100 r=r->ch[r->data
              
               ch[0];107 if (r==null) return null;108 while (r->ch[1]!=null) r=r->ch[1];109 return r;110 }111 SplayNode *suc()112 {113 SplayNode *r=Root->ch[1];114 if (r==null) return null;115 while (r->ch[0]!=null) r=r->ch[0];116 return r;117 }118 void del(int v)119 {120 find(v);121 SplayNode *q=pre();122 SplayNode *p=suc();123 if (q==null && p==null)124 if (Root->num==1) Root=null;125 else Root->num--,Root->updata();126 if (q==null)127 {128 splay(p,null);129 if (Root->ch[0]->num==1) Root->ch[0]=null,Root->updata();130 else Root->ch[0]->num--,splay(Root->ch[0],null);131 return;132 }133 if (p==null)134 {135 splay(q,null);136 if (Root->ch[1]->num==1) Root->ch[1]=null,Root->updata(); 137 else Root->ch[1]->num--,splay(Root->ch[1],null);138 return;139 }140 splay(q,null);141 splay(p,q);142 if (p->ch[0]->num==1) p->ch[0]=null,p->updata();143 else p->ch[0]->num--,splay(p->ch[0],null);144 return;145 }146 }147 void solve()148 {149 int temp,x;150 scanf("%d",&n);151 for (int i=1;i<=n;i++)152 {153 scanf("%d%d",&temp,&x);154 if (temp==1) Splay::insert(x);155 if (temp==2) Splay::del(x);156 if (temp==3) printf("%d\n",Splay::find(x)->ch[0]->size+1);157 if (temp==4) printf("%d\n",Splay::Kth(x)->data);158 if (temp==5) 159 {160 Splay::insert(x);161 printf("%d\n",Splay::pre()->data);162 Splay::del(x);163 }164 if (temp==6)165 { 166 Splay::insert(x);167 printf("%d\n",Splay::suc()->data);168 Splay::del(x);169 }170 }171 }172 int main()173 {174 Splay::MakeTree();175 solve(); 176 return 0;177 }