3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec

Memory Limit: 128 MB

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]

【题解】

平衡树模板题目。

1 #include
        
           2 using namespace std;  3 const int N=100010;  4 int fa[N],ch[N][2],root,k[N],ind=0,size[N];  5 void zig(int x) {    6     int y=fa[x],z=fa[y];    7     fa[y]=x;  8     fa[x]=z;    9     ch[y][0]=ch[x][1],fa[ch[x][1]]=y,ch[x][1]=y;   10     if (y==ch[z][0]) ch[z][0]=x;   11     else ch[z][1]=x;   12     size[y]=size[ch[y][0]]+size[ch[y][1]]+1;  13 }   14 void zag(int x) {   15     int y=fa[x],z=fa[y];   16     fa[y]=x,fa[x]=z;  17     ch[y][1]=ch[x][0],fa[ch[x][0]]=y,ch[x][0]=y;   18     if (y==ch[z][0]) ch[z][0]=x;   19     else ch[z][1]=x;   20     size[y]=size[ch[y][0]]+size[ch[y][1]]+1;  21 }   22 void splay(int x,int s) { 23     while (fa[x]!=s) {   24         int y=fa[x],z=fa[y];   25         if (z==s) {   26             if (x==ch[y][0]) zig(x);   27             else zag(x);   28             break;   29         }   30         if (y==ch[z][0]) { 31             if (x==ch[y][0]) zig(y),zig(x);   32             else zag(x),zig(x);   33         }   34         else {   35             if (x==ch[y][1]) zag(y),zag(x);   36             else zig(x),zag(x);   37         }   38     }   39     size[x]=size[ch[x][0]]+size[ch[x][1]]+1;  40     if (s==0) root=x; 41 }   42 inline void newnode(int &x,int fax,int key) { 43     x=++ind; 44     ch[x][0]=ch[x][1]=0; 45     fa[x]=fax; 46     k[x]=key; 47 } 48 inline int search(int w) { 49     int p,x=root; 50     while(x) { 51         p=x; 52         if(k[x]>w) x=ch[x][0]; 53         else x=ch[x][1]; 54     } 55     return p; 56 } 57 inline void ins(int w){ 58     if (root==0) { 59         newnode(root,0,w); 60         return ; 61     } 62     int i=search(w); 63     if(w
         
          w) {x=ch[x][0];continue;} 71         if (k[x]
          
           =kth) return findkth(ch[x][0],kth);105     else return findkth(ch[x][1],kth-s-1);106 }107 int getp(int w) {108     int y=getsm(w);109     ins(w);110     if(y!=-1) splay(y,0);111     int ans=getmax(ch[root][0]);112     del(w);113     return k[ans];114 }115 int getn(int w) {116     ins(w);117     int ans=getmin(ch[root][1]);118     del(w);119     return k[ans];120 }121 int main() {122     int q;123     root=0;124     ins(-5000000);ins(5000000);125     scanf("%d",&q);  126     while (q--) {  127         int x,k;  128         scanf("%d%d",&x,&k);  129         if (x==1) ins(k);  130         else if (x==2) del(k);  131         else if (x==3) printf("%d\n",ffind(k));  132         else if (x==4) printf("%d\n",findkth(root,k+1));  133         else if (x==5) printf("%d\n",getp(k));  134         else if (x==6) printf("%d\n",getn(k));  135     }136     return 0;137 }
          
         
        

还是习惯分开来写Zig-Zag