<范浩强treap>-函数式平衡树
范好强treap是一种毒瘤treap，它并不用通过旋转来达到平衡，它主要有两种操作：
merge(x,y):将x的子树和y的子树合并起来；｛注意：merge操作中，x子树中的最大值永远会小于等于y子树中的最小值
所以在merge的过程中只需要考虑随机值，而不需考虑key值｝所以merge时要不就x连接在y的左儿子，
要不就y连接在x的右儿子，这时就需通过随机值来确定哪个为儿子。
1 int merge(int x,int y){ 2 //printf("merge:%d %d\n",x,y); 3 if(!x||!y) return x+y; 4 else{ 5 if(t[x].fix split(k,x,y):将小于等于k值的数分离到以x为根的子树中，另外一部分分离到y；只需判断当前节点与k的关系，
若小于等于K,则它的左儿子就一定小于k，但右儿子就不一定了；若大于K,则它的右儿子就一定大于k，左儿子就不一定了。
1 void split(int now,int k,int &x,int &y){ 2 //printf("split:%d %d\n",x,y); 3 if(!now) x=y=0; 4 else{ 5 if(t[now].key<=k){ 6 x=copynode(now); 7 split(t[x].son[1],k,t[x].son[1],y); 8 } 9 else{10 y=copynode(now);11 split(t[y].son[0],k,x,t[y].son[0]);12 }13 update(x);14 update(y);15 }16 }
以下的操作均是通过merge和split实现的：
《insert》——插入
设插入的值为k,只需要把当前的树split(k,x,y)，k单独一棵树，然后再merge(k,x),最后merge(merge(k,x),y);
1 void insert(int bb,int val){2 int x,y,z;3 x=y=z=0;4 split(root[bb],val,x,y);5 z=newnode(val);6 root[bb]=merge(merge(x,z),y);7 } 《delet》——删除
只需要先把树分成大于删除值与小于等于删除值两部分z，x，再在x中分离出小于删除值与等于删除值的树x,y，在y子树中，由于我们只要删除一个数，
所以只需删除y中的根节点，再把y的左右儿子合并起来。
1 void del(int bb,int val){2 int x=0,y=0,z=0;3 split(root[bb],val,x,z);4 split(x,val-1,x,y);5 y=merge(t[y].son[0],t[y].son[1]);6 root[bb]=merge(merge(x,y),z);7 } 求第k值的排名(比它小的数+1)——getkth
分离出小于k的数存在树x中，然后排名等于x的子树+1。
1 int getkth(int bb,int val){2 int x,y,ret;3 split(root[bb],val-1,x,y);4 ret=t[x].sz+1;5 return ret;6 } 求排名为k的数——getval
用一个while循环即可获得排名为k的值emm 。
1 int getpos(int now,int k){ 2 while(1){ 3 if(k<=t[t[now].son[0]].sz) now=t[now].son[0]; 4 else if(k==t[t[now].son[0]].sz+1) { return now;} 5 else{ 6 k-=t[t[now].son[0]].sz+1; 7 now=t[now].son[1]; 8 } 9 }10 }11 int getval(int now,int k){12 int x;13 x=getpos(now,k);14 //printf("pos:%d\n",x);15 return t[x].key;16 } 求val前驱——getpre
先split(val-1,x,y)，然后转换为求排名为k(sz[x])的数即可。
1 int getpre(int bb,int val){2 int x,y,k,ret;3 split(root[bb],val-1,x,y);4 if(x) k=t[x].sz;5 else return -2147483647;6 ret=getval(x,k);7 return ret;8 } 求val后继——getsuc
原理与求pre一样吧嗯嗯。
1 int getsuc(int bb,int val){2 int x,y,ret;3 split(root[bb],val,x,y);4 if(!y) return 2147483647;5 ret=getval(y,1);6 return ret;7 } luogu 3835:
1 #include2 #include 3 #include 4 #define maxn 500009 5 using namespace std; 6 struct node{ 7 int son[2]; 8 int fix,key,sz; 9 }t[maxn*50]; 10 int root[maxn],cnt=1; 11 int copynode(int x){ 12 cnt++; 13 t[cnt]=t[x]; 14 return cnt; 15 } 16 void update(int cur){ 17 if(cur)t[cur].sz=t[t[cur].son[0]].sz+t[t[cur].son[1]].sz+1; 18 } 19 int newnode(int val){ 20 cnt++; 21 t[cnt].son[0]=t[cnt].son[1]=0; 22 t[cnt].key=val; 23 t[cnt].sz=1; 24 t[cnt].fix=rand(); 25 return cnt; 26 } 27 void split(int now,int k,int &x,int &y){ 28 //printf("split:%d %d\n",x,y); 29 if(!now) x=y=0; 30 else{ 31 if(t[now].key<=k){ 32 x=copynode(now); 33 split(t[x].son[1],k,t[x].son[1],y); 34 } 35 else{ 36 y=copynode(now); 37 split(t[y].son[0],k,x,t[y].son[0]); 38 } 39 update(x); 40 update(y); 41 } 42 } 43 int merge(int x,int y){ 44 //printf("merge:%d %d\n",x,y); 45 if(!x||!y) return x+y; 46 else{ 47 if(t[x].fix