fhq Treap（无旋Treap）

先吹一波fhq dalao，竟然和我一个姓，我真是给他丢脸。

昨天treap就搞了一下午，感觉自己弱爆了。然后今天上午又看了一个上午的无旋treap再次懵逼，我太弱了，orzorz。

所以写个博客防止自己忘了吧（其实就是贴个代码）。

其实fhq treap中最重要的操作就是split和merge，这样就避免了普通treap中的zig和zag，而且各种查询十分方便，基本查个排名就出来了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int N=1e5+;

 int root,tot;

 struct Treap{

     int l,r,dat,val,size;

 }tr[N];

 void update(int p){tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+;}

 int New(int val){

     int x=++tot;

     tr[x].val=val;

     tr[x].dat=rand();

     tr[x].size=;

     return x;

 }

 void merge(int &root,int a,int b){

     if(!a||!b){

         root=a+b;

         return ;

     }

     if(tr[a].dat<tr[b].dat){//a shi baba

         root=a;

         merge(tr[root].r,tr[a].r,b);

     }

     else{

         root=b;

         merge(tr[root].l,a,tr[b].l);

     }

     update(root);

 }

 void split(int x,int &a,int &b,int val){

     if(!x){

         a=b=;

         return ;

     }

     if(tr[x].val<=val){

         a=x;

         split(tr[x].r,tr[a].r,b,val);

     }

     else{

         b=x;

         split(tr[x].l,a,tr[b].l,val);

     }

     update(x);

 }

 int getrankbyval(int &root,int val){

     int x=,y=;

     split(root,x,y,val-);

     int ans=tr[x].size+;

     merge(root,x,y);

     return ans;

 }

 int getvalbyrank(int &root,int rank){

     int x=root;

     while(tr[tr[x].l].size+!=rank){

         if(rank<=tr[tr[x].l].size) x=tr[x].l;

         else rank-=(tr[tr[x].l].size+),x=tr[x].r;

     }

     return tr[x].val;

 }

 void insert(int &root,int val){

     int x=,y=;

     split(root,x,y,val);

     merge(x,x,New(val));

     merge(root,x,y);

 }

 void remove(int &root,int val){

     int x=,y=,z=;

     split(root,x,y,val);

     split(x,x,z,val-);

     merge(z,tr[z].l,tr[z].r);

     merge(x,x,z);

     merge(root,x,y);

 }

 int pre(int &root,int val){

     int x=,y=;

     split(root,x,y,val-);

     int ans=getvalbyrank(x,tr[x].size);

     merge(root,x,y);

     return ans;

 }

 int next(int &root,int val){

     int x=,y=;

     split(root,x,y,val);

     int ans=getvalbyrank(y,);

     merge(root,x,y);

     return ans;

 }

 int main(){

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         int opt,x;

         scanf("%d%d",&opt,&x);

         if(opt==) insert(root,x);

         else if(opt==) remove(root,x);

         else if(opt==) printf("%d\n",getrankbyval(root,x));

         else if(opt==) printf("%d\n",getvalbyrank(root,x));

         else if(opt==) printf("%d\n",pre(root,x));

         else if(opt==) printf("%d\n",next(root,x));

     }

 }

明天考试，我好慌，我好慌。

马上分机房，我肯定去菜机房了，我好慌，我好慌。

加油吧，为了自己的梦想

Mi corazón pertenece a Barcelona para siempre.