BZOJ 3224 TYVJ 1728 普通平衡树 [Treap树模板]

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7390 Solved: 3122
[Submit][Status][Discuss]

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]

数据如下http://pan.baidu.com/s/1jHMJwO2

treap的模板题，涉及了treap的各种操作

操作函数中运用了传引用的方式改变上一层结点的子节点值，很方便

  1 /*by SilverN*/
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<algorithm>
  7 using namespace std;
  8 int n;
  9 struct treap{
 10     int l,r;//左右子树 
 11     int val,ct;//值 重复次数 
 12     int size,rand;//管控数量，随机权值 
 13 }t[120000];
 14 int root=0,cnt=0;
 15 int ans;
 16 void update(int k){
 17     t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].ct;
 18 }
 19 void lt(int &k){//左旋 
 20     int now=t[k].r;
 21     t[k].r=t[now].l;
 22     t[now].l=k;
 23     t[now].size=t[k].size;
 24     update(k);
 25     k=now;
 26     return;
 27 }
 28 void rt(int &k){
 29     int now=t[k].l;
 30     t[k].l=t[now].r;
 31     t[now].r=k;
 32     t[now].size=t[k].size;
 33     update(k);
 34     k=now;
 35     return;
 36 }
 37 void insert(int &k,int x){//&k是为了建新节点  x为插入值
 38     if(k==0){//建新节点 
 39         t[++cnt].val=x;
 40         t[cnt].size=1;
 41         t[cnt].ct=1;
 42         t[cnt].rand=rand();
 43         k=cnt;
 44         return;
 45     } 
 46     t[k].size++;
 47     if(t[k].val==x) t[k].ct++;//与节点等值 
 48     else if(x>t[k].val){
 49         insert(t[k].r,x);
 50         if(t[t[k].r].rand<t[k].rand) lt(k);
 51     }else{//x<t[k].val
 52         insert(t[k].l,x);
 53         if(t[t[k].l].rand<t[k].rand) rt(k);
 54     }
 55     return;
 56 }
 57 void del(int &k,int x){
 58     if(k==0)return;
 59     if(t[k].val==x){
 60         if(t[k].ct>1){t[k].ct--;t[k].size--;return;}
 61         if(t[k].l*t[k].r==0)k=t[k].l+t[k].r;//如果k是链结点(只有一个子节点)，由其子节点补位 
 62         else{
 63             if(t[t[k].l].rand<t[t[k].r].rand){
 64                 rt(k);
 65                 del(k,x);
 66             }
 67             else{
 68                 lt(k);
 69                 del(k,x);
 70             }
 71         }
 72         return;
 73         
 74     }
 75     t[k].size--;
 76     if(x>t[k].val)del(t[k].r,x);
 77     if(x<t[k].val)del(t[k].l,x);
 78     return;
 79 }
 80 void ask_p(int k,int x,int mode){//前驱 //mode==1 ->前驱   mode==2 ->后驱 
 81     if(mode==1){
 82         if(!k)return;
 83         if(t[k].val<x){//依照二叉树的性质，要找小的往左查，要找大的往右查 
 84             ans=t[k].val;
 85             ask_p(t[k].r,x,1);
 86         }else ask_p(t[k].l,x,1);
 87         return;
 88     }
 89     if(mode==2){
 90         if(!k)return;
 91         if(t[k].val>x){
 92             ans=t[k].val;
 93             ask_p(t[k].l,x,2);
 94         }else ask_p(t[k].r,x,2);
 95     }
 96     return;
 97 }
 98 int ask_rank(int k,int x){//已知数字问排名 
 99     if(!k)return 0;
100     if(t[k].val==x)return t[t[k].l].size+1;
101     if(t[k].val<x)return t[k].ct+t[t[k].l].size+ask_rank(t[k].r,x);
102     else return ask_rank(t[k].l,x);
103 }
104 int ask_num(int k,int x){// 已知排名问数字 
105     if(!k)return 0;
106     if(x<=t[t[k].l].size)return ask_num(t[k].l,x);//排名小于左子树包含结点数量，则往左查 
107     if(x>t[t[k].l].size+t[k].ct)return ask_num(t[k].r,x-t[t[k].l].size-t[k].ct);
108     //排名大于“左子树结点数加父结点重复数”，则往右查 
109     else return t[k].val;//否则返回父结点值 
110 }
111 int main(){
112     int opt,x;
113     scanf("%d",&n);
114     while(n--){
115         scanf("%d%d",&opt,&x);
116         switch(opt){
117             case 1:    insert(root,x);    break;
118             case 2: del(root,x); break;                
119             case 3: printf("%d
",ask_rank(root,x)); break;
120             case 4: printf("%d
",ask_num(root,x)); break;        
121             case 5: ask_p(root,x,1);printf("%d
",ans);break;//前驱 
122             case 6: ask_p(root,x,2);printf("%d
",ans);break;//前驱 
123         }
124 //        for(int i=1;i<=cnt;i++)printf("%d ",t[i].val);
125 //        cout<<endl;
126     }
127     return 0;
128 }