普通平衡树

P1375 - [Tyvj 1728]普通平衡树

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

Sample Output

Hint

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

这真是一道非常优(bian)秀(tai)的数据结构练习题。

６个平衡树操作。

关于查询ｘ这个数的排名，一开始写了个鬼畜做法，ＷＡ飞，主要是有相同的数取最小感觉不好处理。

可以把ｘ的前驱找出来，然后旋转到root,那么root的左子树大小加１就是答案了。

还有查询排名为x的数，从根节点开始找，先判断ｘ有没有到０，到０了直接输出。

若左子树的size小于ｘ，则ｘ减去size,并找右子树。否则找左子树。

还有一些细节要注意，就是找前驱和后继的时候要写<=和>=，因为会有重复的数。

删除操作时，找到前驱和后继了，旋转后要在后继的左子树中删除一个结点，因为题目说有重复的只删一个。
这时就可以一直往下找到叶子结点，此时遍历到的每个结点的size都要-1。

  1 #include<set>
  2 #include<map>
  3 #include<queue>
  4 #include<stack>
  5 #include<ctime>
  6 #include<cmath>
  7 #include<string>
  8 #include<vector>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<cstring>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define inf 1999999999
 15 #define maxn 100010
 16 using namespace std;
 17 int key[maxn],pre[maxn],ch[maxn][2],size[maxn],tot=0,root=0;
 18 void newnode(int &x,int fa,int keyy){
 19   x=++tot;
 20   key[x]=keyy;
 21   pre[x]=fa;
 22   ch[x][1]=ch[x][0]=0;
 23 }
 24 void Rotate(int x,int kind){
 25   int y=pre[x];
 26   ch[y][!kind]=ch[x][kind];
 27   pre[ch[x][kind]]=y;
 28   if(pre[y])
 29     ch[pre[y]][ch[pre[y]][1]==y]=x;
 30   pre[x]=pre[y];
 31   ch[x][kind]=y;
 32   pre[y]=x;
 33   size[y]=size[ch[y][0]]+size[ch[y][1]]+1;
 34   size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
 35 }
 36 void Splay(int r,int goal){
 37   while(pre[r]!=goal){
 38     if(pre[pre[r]]==goal)
 39       Rotate(r,ch[pre[r]][0]==r);
 40     else{
 41       int y=pre[r];
 42       int kind=ch[pre[y]][0]==y;
 43       if(ch[y][kind]==r){
 44     Rotate(r,!kind);  
 45     Rotate(r,kind);
 46       }
 47       else{
 48     Rotate(y,kind);
 49     Rotate(r,kind);
 50       }
 51     }
 52   }
 53   if(goal==0) root=r;
 54 }
 55 void Insert(int k){
 56   while(ch[root][key[root]<k]){
 57     size[root]++;
 58     root=ch[root][key[root]<k];
 59   }
 60   size[root]++;
 61   newnode(ch[root][key[root]<k],root,k);
 62   size[ch[root][key[root]<k]]++;
 63   Splay(ch[root][key[root]<k],0);
 64 }
 65 void find_pre(int x,int k,int &ans){
 66   if(!x) return;
 67   if(key[x]<k){ans=x;find_pre(ch[x][1],k,ans);return;}
 68   if(key[x]>=k){find_pre(ch[x][0],k,ans);return;}
 69 }
 70 void find_nex(int x,int k,int &ans){
 71   if(!x) return;
 72   if(key[x]<=k){find_nex(ch[x][1],k,ans);return;}
 73   if(key[x]>k){ans=x;find_nex(ch[x][0],k,ans);return;}
 74 }
 75 void Earse(int k){
 76   int prek=root;find_pre(root,k,prek);
 77   int nexk=root;find_nex(root,k,nexk);
 78   Splay(prek,0);Splay(nexk,prek);
 79   int tmp=ch[nexk][0];
 80   size[nexk]--;
 81   while(ch[tmp][0] || ch[tmp][1]){
 82     size[tmp]--;
 83     if(ch[tmp][0]) tmp=ch[tmp][0];
 84     else tmp=ch[tmp][1]; 
 85   }
 86   if(ch[pre[tmp]][0]==tmp) ch[pre[tmp]][0]=0;
 87   else ch[pre[tmp]][1]=0;
 88 }
 89 void Find_rank(int k){
 90   int prek=root;find_pre(root,k,prek);
 91   Splay(prek,0);
 92   printf("%d
",size[ch[root][0]]+1);
 93 }
 94 void Find_num(int k){
 95   int rt=root;
 96   while(rt){
 97     if(size[ch[rt][0]]+1==k){printf("%d
",key[rt]);return;}
 98     if(size[ch[rt][0]]<k)k-=(size[ch[rt][0]]+1),rt=ch[rt][1];
 99     else rt=ch[rt][0];
100   }
101 }
102 void Query_pre(int x,int k,int &ans){
103   if(!x) return;
104   if(key[x]<k){ans=key[x];Query_pre(ch[x][1],k,ans);return;}
105   if(key[x]>=k){Query_pre(ch[x][0],k,ans);return;}
106 }
107 void Query_nex(int x,int k,int &ans){
108   if(!x) return;
109   if(key[x]<=k){Query_nex(ch[x][1],k,ans);return;}
110   if(key[x]>k){ans=key[x];Query_nex(ch[x][0],k,ans);return;}
111 }
112 int main()
113 {
114   freopen("!.in","r",stdin);
115   freopen("!.out","w",stdout);
116   int n,type,x;
117   scanf("%d",&n);
118   newnode(root,0,-inf),Insert(inf);
119   for(int i=1;i<=n;i++){
120     scanf("%d%d",&type,&x);
121     if(type==1) Insert(x);
122     if(type==2) Earse(x);
123     if(type==3) Find_rank(x);
124     if(type==4) Find_num(x+1);
125     if(type==5){
126       int ans=key[root];
127       Query_pre(root,x,ans);
128       printf("%d
",ans);
129     }
130     if(type==6){
131       int ans=key[root];
132       Query_nex(root,x,ans);
133       printf("%d
",ans);
134     }
135   }
136   return 0;
137 }