(treap)[bzoj3224][洛谷3369][cogs1829]Tyvj 1728 普通平衡树-白红宇

(treap)[bzoj3224][洛谷3369][cogs1829]Tyvj 1728 普通平衡树

阅读量：4349 次

发布时间：2019-06-07

本文共 7201 字，大约阅读时间需要 24 分钟。

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

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.每个数的数据范围：[-2e9,2e9]

Source

STL用法练手题。。。（手动滑稽）

这数据我给满分

(感谢...)

1 // It is made by XZZ 2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define rep(a,b,c) for(rg int a=b;a<=c;a++) 7 #define drep(a,b,c) for(rg int a=b;a>=c;a--) 8 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a]) 9 #define il inline10 #define rg register11 #define vd void12 typedef long long ll;13 il int gi(){14     rg int x=0,f=1;rg char ch=getchar();15     while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();16     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();17     return x*f;18 }19 vector
          
           A;20 int main(){21     int n=gi(),opt,x;22     while(n--){23     opt=gi(),x=gi();24     if(opt==1)A.insert(upper_bound(A.begin(),A.end(),x),x);25     else if(opt==2)A.erase(lower_bound(A.begin(),A.end(),x));26     else if(opt==3)printf("%d\n",lower_bound(A.begin(),A.end(),x)-A.begin()+1);27     else if(opt==4)printf("%d\n",A[x-1]);28     else if(opt==5)printf("%d\n",*(lower_bound(A.begin(),A.end(),x)-1));29     else printf("%d\n",*upper_bound(A.begin(),A.end(),x));30     }31     return 0;32 }

View Code

（学习treap中，到时候再发）

更新：

液我A了！！！

先上代码

1 // It is made by XZZ  2 #include
       
          3 using namespace std;  4 #define rep(a,b,c) for(rg int a=b;a<=c;a++)  5 #define drep(a,b,c) for(rg int a=b;a>=c;a--)  6 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])  7 #define il inline  8 #define rg register  9 #define vd void 10 #define Ls tree[now].ls 11 #define Rs tree[now].rs 12 typedef long long ll; 13 il int gi(){ 14     rg int x=0,f=1;rg char ch=getchar(); 15     while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); 16     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 17     return x*f; 18 } 19 struct node{ 20     int ls,rs,value,rand,sum,size; 21     node(){ls=rs=value=rand=sum=size=0;} 22 }tree[100001]; 23 int root=0,siz=0; 24 ll seed=19260817; 25 il int Rand(){
     return seed=seed*48271LL%2147483647;} 26 il vd reset(int now){ 27     tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum; 28 } 29 il vd lrot(int&now){ 30     int ls=tree[now].ls; 31     tree[now].ls=tree[ls].rs,tree[ls].rs=now; 32     tree[ls].size=tree[now].size;reset(now);now=ls; 33 } 34 il vd rrot(int&now){ 35     int rs=tree[now].rs; 36     tree[now].rs=tree[rs].ls,tree[rs].ls=now; 37     tree[rs].size=tree[now].size;reset(now);now=rs; 38 } 39 il vd ins(int&now,int num){ 40     if(now==0){ 41     ++siz,now=siz,tree[now].size=tree[now].sum=1,tree[now].value=num,tree[now].rand=Rand(); 42     return; 43     } 44     ++tree[now].size; 45     if(tree[now].value==num)++tree[now].sum; 46     else if(num
        
         1){--tree[now].sum,--tree[now].size;return;} 58     if(!Ls||!Rs)now=Ls|Rs; 59     else if(tree[Ls].rand
         
          tree[now].value)return tree[Ls].size+tree[now].sum+getrank(Rs,num); 71     else return getrank(Ls,num); 72 } 73 il int getnum(int now,int num){ 74     if(num<=tree[Ls].size)return getnum(Ls,num); 75     else if(num>tree[Ls].size+tree[now].sum)return getnum(Rs,num-tree[Ls].size-tree[now].sum); 76     else return tree[now].value; 77 } 78 int ans; 79 il vd lower(int now,int num){ 80     if(now==0)return; 81     if(tree[now].value
          
           num)ans=now,upper(Ls,num); 87     else upper(Rs,num); 88 } 89 int main(){ 90     int n=gi(),opt,x; 91     while(n--){ 92     opt=gi(),x=gi(); 93     switch(opt){ 94         case 1:ins(root,x);break; 95         case 2:del(root,x);break; 96         case 3:printf("%d\n",getrank(root,x));break; 97         case 4:printf("%d\n",getnum(root,x));break; 98         case 5:ans=0,lower(root,x),printf("%d\n",tree[ans].value);break; 99         case 6:ans=0,upper(root,x),printf("%d\n",tree[ans].value);break;100     }101     }102     return 0;103 }

View Code

因为太短了，写一点东西。。。

treap==tree+heap

因为二叉查找树很难平衡，所以加一个随机权值，当作一个堆维护

所以treap既有tree性质又有heap性质

当heap性质被破坏后用旋转来维护

我们还可以把函数写成非递归的。。。

1 // It is made by XZZ  2 #include
       
          3 using namespace std;  4 #define rep(a,b,c) for(rg int a=b;a<=c;a++)  5 #define drep(a,b,c) for(rg int a=b;a>=c;a--)  6 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])  7 #define il inline  8 #define rg register  9 #define vd void 10 #define Ls tree[now].ls 11 #define Rs tree[now].rs 12 typedef long long ll; 13 il int gi(){ 14     rg int x=0,f=1;rg char ch=getchar(); 15     while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); 16     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 17     return x*f; 18 } 19 struct node{ 20     int ls,rs,value,rand,sum,size; 21     node(){ls=rs=value=rand=sum=size=0;} 22 }tree[100001]; 23 int root=0,siz=0; 24 ll seed=19260817; 25 il int Rand(){
     return seed=seed*48271LL%2147483647;} 26 il vd reset(int now){ 27     tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum; 28 } 29 il vd lrot(int&now){ 30     int ls=tree[now].ls; 31     tree[now].ls=tree[ls].rs,tree[ls].rs=now; 32     tree[ls].size=tree[now].size;reset(now);now=ls; 33 } 34 il vd rrot(int&now){ 35     int rs=tree[now].rs; 36     tree[now].rs=tree[rs].ls,tree[rs].ls=now; 37     tree[rs].size=tree[now].size;reset(now);now=rs; 38 } 39 il vd ins(int&now,int num){ 40     if(now==0){ 41     ++siz,now=siz,tree[now].size=tree[now].sum=1,tree[now].value=num,tree[now].rand=Rand(); 42     return; 43     } 44     ++tree[now].size; 45     if(tree[now].value==num)++tree[now].sum; 46     else if(num
        
         1){--tree[now].sum,--tree[now].size;return;} 58     if(!Ls||!Rs)now=Ls|Rs; 59     else if(tree[Ls].rand
         
          tree[now].value)Rank+=tree[Ls].size+tree[now].sum,now=Rs; 71     else now=Ls; 72 } 73 il int getnum(int now,int num){ 74     while(1) 75         if(num<=tree[Ls].size)now=Ls; 76         else if(num>tree[Ls].size+tree[now].sum)num-=tree[Ls].size+tree[now].sum,now=Rs; 77         else return tree[now].value; 78 } 79 il int lower(int now,int num){ 80     int ret; 81     while(now)if(tree[now].value
          
           num)ret=tree[now].value,now=Ls; 88         else now=Rs; 89     return ret; 90 } 91 int main(){ 92     freopen("phs.in","r",stdin); 93     freopen("phs.out","w",stdout); 94     int n=gi(),opt,x; 95     while(n--){ 96     opt=gi(),x=gi(); 97     switch(opt){ 98         case 1:ins(root,x);break; 99         case 2:del(root,x);break;100             case 3:printf("%d\n",getrank(root,x));break;101         case 4:printf("%d\n",getnum(root,x));break;102         case 5:printf("%d\n",lower(root,x));break;103         case 6:printf("%d\n",upper(root,x));break;104     }105     }106     return 0;107 }