(treap)[bzoj3224][洛谷3369][cogs1829]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

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

Source

平衡树

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

这数据我给满分

(感谢hzwer...)

 // It is made by XZZ

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define rep(a,b,c) for(rg int a=b;a<=c;a++)

 #define drep(a,b,c) for(rg int a=b;a>=c;a--)

 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

 #define il inline

 #define rg register

 #define vd void

 typedef long long ll;

 il int gi(){

     rg int x=,f=;rg char ch=getchar();

     while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return x*f;

 }

 vector<int>A;

 int main(){

     int n=gi(),opt,x;

     while(n--){

     opt=gi(),x=gi();

     if(opt==)A.insert(upper_bound(A.begin(),A.end(),x),x);

     else if(opt==)A.erase(lower_bound(A.begin(),A.end(),x));

     else if(opt==)printf("%d\n",lower_bound(A.begin(),A.end(),x)-A.begin()+);

     else if(opt==)printf("%d\n",A[x-]);

     else if(opt==)printf("%d\n",*(lower_bound(A.begin(),A.end(),x)-));

     else printf("%d\n",*upper_bound(A.begin(),A.end(),x));

     }

     return ;

 }

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

更新：

液我A了！！！

先上代码

 // It is made by XZZ

 #include<cstdio>

 using namespace std;

 #define rep(a,b,c) for(rg int a=b;a<=c;a++)

 #define drep(a,b,c) for(rg int a=b;a>=c;a--)

 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

 #define il inline

 #define rg register

 #define vd void

 #define Ls tree[now].ls

 #define Rs tree[now].rs

 typedef long long ll;

 il int gi(){

     rg int x=,f=;rg char ch=getchar();

     while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return x*f;

 }

 struct node{

     int ls,rs,value,rand,sum,size;

     node(){ls=rs=value=rand=sum=size=;}

 }tree[];

 int root=,siz=;

 ll seed=;

 il int Rand(){return seed=seed*48271LL%;}

 il vd reset(int now){

     tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum;

 }

 il vd lrot(int&now){

     int ls=tree[now].ls;

     tree[now].ls=tree[ls].rs,tree[ls].rs=now;

     tree[ls].size=tree[now].size;reset(now);now=ls;

 }

 il vd rrot(int&now){

     int rs=tree[now].rs;

     tree[now].rs=tree[rs].ls,tree[rs].ls=now;

     tree[rs].size=tree[now].size;reset(now);now=rs;

 }

 il vd ins(int&now,int num){

     if(now==){

     ++siz,now=siz,tree[now].size=tree[now].sum=,tree[now].value=num,tree[now].rand=Rand();

     return;

     }

     ++tree[now].size;

     if(tree[now].value==num)++tree[now].sum;

     else if(num<tree[now].value){

     ins(Ls,num);

     if(tree[Ls].rand<tree[now].rand)lrot(now);

     }else{

     ins(Rs,num);

     if(tree[Rs].rand<tree[now].rand)rrot(now);

     }

 }

 il vd del(int&now,int num){

     if(now==)return;

     if(tree[now].value==num){

     if(tree[now].sum>){--tree[now].sum,--tree[now].size;return;}

     if(!Ls||!Rs)now=Ls|Rs;

     else if(tree[Ls].rand<tree[Rs].rand)lrot(now),del(now,num);

     else rrot(now),del(now,num);

     return;

     }

     --tree[now].size;

     if(num<tree[now].value)del(Ls,num);

     else del(Rs,num);

 }

 il int getrank(int now,int num){

     if(now==)return ;

     if(tree[now].value==num)return tree[Ls].size+;

     if(num>tree[now].value)return tree[Ls].size+tree[now].sum+getrank(Rs,num);

     else return getrank(Ls,num);

 }

 il int getnum(int now,int num){

     if(num<=tree[Ls].size)return getnum(Ls,num);

     else if(num>tree[Ls].size+tree[now].sum)return getnum(Rs,num-tree[Ls].size-tree[now].sum);

     else return tree[now].value;

 }

 int ans;

 il vd lower(int now,int num){

     if(now==)return;

     if(tree[now].value<num)ans=now,lower(Rs,num);

     else lower(Ls,num);

 }

 il vd upper(int now,int num){

     if(now==)return;

     if(tree[now].value>num)ans=now,upper(Ls,num);

     else upper(Rs,num);

 }

 int main(){

     int n=gi(),opt,x;

     while(n--){

     opt=gi(),x=gi();

     switch(opt){

         case :ins(root,x);break;

         case :del(root,x);break;

         case :printf("%d\n",getrank(root,x));break;

         case :printf("%d\n",getnum(root,x));break;

         case :ans=,lower(root,x),printf("%d\n",tree[ans].value);break;

         case :ans=,upper(root,x),printf("%d\n",tree[ans].value);break;

     }

     }

     return ;

 }

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

treap==tree+heap

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

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

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

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

 // It is made by XZZ

 #include<cstdio>

 using namespace std;

 #define rep(a,b,c) for(rg int a=b;a<=c;a++)

 #define drep(a,b,c) for(rg int a=b;a>=c;a--)

 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

 #define il inline

 #define rg register

 #define vd void

 #define Ls tree[now].ls

 #define Rs tree[now].rs

 typedef long long ll;

 il int gi(){

     rg int x=,f=;rg char ch=getchar();

     while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return x*f;

 }

 struct node{

     int ls,rs,value,rand,sum,size;

     node(){ls=rs=value=rand=sum=size=;}

 }tree[];

 int root=,siz=;

 ll seed=;

 il int Rand(){return seed=seed*48271LL%;}

 il vd reset(int now){

     tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum;

 }

 il vd lrot(int&now){

     int ls=tree[now].ls;

     tree[now].ls=tree[ls].rs,tree[ls].rs=now;

     tree[ls].size=tree[now].size;reset(now);now=ls;

 }

 il vd rrot(int&now){

     int rs=tree[now].rs;

     tree[now].rs=tree[rs].ls,tree[rs].ls=now;

     tree[rs].size=tree[now].size;reset(now);now=rs;

 }

 il vd ins(int&now,int num){

     if(now==){

     ++siz,now=siz,tree[now].size=tree[now].sum=,tree[now].value=num,tree[now].rand=Rand();

     return;

     }

     ++tree[now].size;

     if(tree[now].value==num)++tree[now].sum;

     else if(num<tree[now].value){

     ins(Ls,num);

     if(tree[Ls].rand<tree[now].rand)lrot(now);

     }else{

     ins(Rs,num);

     if(tree[Rs].rand<tree[now].rand)rrot(now);

     }

 }

 il vd del(int&now,int num){

     if(now==)return;

     if(tree[now].value==num){

     if(tree[now].sum>){--tree[now].sum,--tree[now].size;return;}

     if(!Ls||!Rs)now=Ls|Rs;

     else if(tree[Ls].rand<tree[Rs].rand)lrot(now),del(now,num);

     else rrot(now),del(now,num);

     return;

     }

     --tree[now].size;

     if(num<tree[now].value)del(Ls,num);

     else del(Rs,num);

 }

 il int getrank(int now,int num){

     int Rank=;

     while(now)if(tree[now].value==num)return tree[Ls].size++Rank;

         else if(num>tree[now].value)Rank+=tree[Ls].size+tree[now].sum,now=Rs;

     else now=Ls;

 }

 il int getnum(int now,int num){

     while()

         if(num<=tree[Ls].size)now=Ls;

         else if(num>tree[Ls].size+tree[now].sum)num-=tree[Ls].size+tree[now].sum,now=Rs;

         else return tree[now].value;

 }

 il int lower(int now,int num){

     int ret;

     while(now)if(tree[now].value<num)ret=tree[now].value,now=Rs;

         else now=Ls;

     return ret;

 }

 il int upper(int now,int num){

     int ret;

     while(now)if(tree[now].value>num)ret=tree[now].value,now=Ls;

         else now=Rs;

     return ret;

 }

 int main(){

     freopen("phs.in","r",stdin);

     freopen("phs.out","w",stdout);

     int n=gi(),opt,x;

     while(n--){

     opt=gi(),x=gi();

     switch(opt){

         case :ins(root,x);break;

         case :del(root,x);break;

             case :printf("%d\n",getrank(root,x));break;

         case :printf("%d\n",getnum(root,x));break;

         case :printf("%d\n",lower(root,x));break;

         case :printf("%d\n",upper(root,x));break;

     }

     }

     return ;

 }

这样在cogs上可以从1.90s下降到1.70s

在洛谷上可以从164ms上升到259ms（大雾）

在bzoj上可以从300ms下降到296ms

所以非递归到底有没有用？？？

巴特西