题解 P3369 【【模板】普通平衡树】

经过主席,duck,kh的指点,bear终于学会了fhq,就写了一篇题解,来纪念一下 首先,第一个问题:fhq是什么? fhq是由fhq巨佬发明的treap,利用分裂和合并,可以做到无旋treap,及可持久化等多项功能 ------------ ## fhq的核心就是分裂与合并 ### 首先是合并: 对于两颗树t1,t2,满足t1中的所有点均<=t2,我们可以按以下规则合并: 1.如果t1,t2中有任意一颗树是空的那么,直接接上即可 2.否则,为了保持平衡,我们rand值,按sz[t1]:sz[t2]的概率来决定是合并到t1,还是t2 3.递归合并,上传 **注意:因为t2的点大于t1,所以合并一定是t2合t1右子树,t1合t2左子树,还有在递归合并时也要注意t1,t2大小** **(简单来说,你可以理解为让小的合并到大的的概率更大)**  ```cpp int hb(int t1,int t2) //合并操作，必须保证t1的点都<=t2 { if(!t1||!t2) return t1+t2; else if((rad()%(sz[t1]+sz[t2]))<sz[t1]) //然它期望均摊到两颗树中 // < t1,t2的期望:sz[t1]:sz[t2] > t1,t2的期望:sz[t2]:sz[t1] //简单来说,就是尽可能让小的和到大的上面,来保证它良好的复杂度 { r[t1]=hb(r[t1],t2); //将t2合并到t1右树（t2>=t1) pup(t1); return t1; } else { l[t2]=hb(t1,l[t2]); //同上 pup(t2); return t2; } } ``` ------------ ### 然后是分裂 分裂有两种,按值分裂和按个数分裂 先讲分裂的总体思路: 如果你的树空了,那么分出来的也一定是空的 然后按判断标准,选择分裂到谁,递归,上传  按值分裂:就是把所有<=w合到x树上,其他的合到y树上 ```cpp void splitv(int k,int w,int &x,int &y) //按值分裂，保证x<=y , 把所有<=w的值都给x,剩下的给y { if(!k) x=y=0; else if(w>=v[k]) //我要的值比当前值大 { x=k; //当前值给小的（x） splitv(r[k],w,r[x],y); //向右子树继续分裂 pup(x); } else { y=k; splitv(l[k],w,x,l[y]); pup(y); } } ``` 按个数分裂:就是把前w个分到x树上,剩下的分到y树上 ```cpp void splits(int k,int w,int &x,int &y) //按个数分裂，保证x<=y,(x就是那前w个) { if(!k) x=y=0; else if(w<=sz[l[k]]) //如果当前个数多余 { y=k; //比w多，一定是在y上的 splits(l[k],w,x,l[y]); //向左子树分裂 pup(y); } else { x=k; splits(r[k],w-sz[l[k]]-1,r[x],y); pup(x); } } ``` ------------ 有了这两个操作,那么剩下的也比较简单了 ------------ 插入:把所有<=x的分裂到一颗树a上,剩下的在另一颗树b上,把a,x,b合并即为所求 ```cpp void ins(int x) //插入 { int t1,t2; splitv(rt,x,t1,t2); //把一棵树分裂成按x分裂成两部分 rt=hb(hb(t1,xj(x)),t2); //再把左边与x合并，再与右边合并 } ``` ------------ 删除:把所有<x的值分裂到一颗树a上,剩下的在b上,再把b上分出一个第一小的数,即为要删的x,剩下的是d,只要把中间这个x忽略,直接合并a,d,就相当于删了一个x ```cpp void del(int x) //删除 { int a,b,c,d; splitv(rt,x-1,a,b); //把它分成两部分（x是右边那部分的最小值） splits(b,1,c,d); //把右边分裂出一个大小为1的点c（x） rt=hb(a,d); //不管c，直接合并a，d（忽略了一个x） } ``` ------------ 剩下的操作你可以按普通treap进行,也可以用分裂合并,读者自想不难,想不出的可以看代码,注释里说的很详细 ------------ 代码: ```cpp #include<bits/stdc++.h> #define il inline using namespace std; const int N = 1e5+5; il int rad(){return 1ll*rand()*19491001%19260817;} struct treep { int l[N],r[N],sz[N],v[N]; int tim,rt; il void pup(int x){sz[x]=sz[l[x]]+sz[r[x]]+1;} il int xj(int x) { tim++; v[tim]=x; sz[tim]=1; return tim; } int hb(int t1,int t2) //合并操作，必须保证t1的点都<=t2 { if(!t1||!t2) return t1+t2; else if((rad()%(sz[t1]+sz[t2]))<sz[t1]) //然它期望均摊到两颗树中 // < t1,t2的期望:sz[t1]:sz[t2] > t1,t2的期望:sz[t2]:sz[t1] //简单来说,就是尽可能让小的和到大的上面,来保证它良好的复杂度 { r[t1]=hb(r[t1],t2); //将t2合并到t1右树（t2>=t1) pup(t1); return t1; } else { l[t2]=hb(t1,l[t2]); //同上 pup(t2); return t2; } } void splitv(int k,int w,int &x,int &y) //按值分裂，保证x<=y , 把所有<=w的值都给x,剩下的给y { if(!k) x=y=0; else if(w>=v[k]) //我要的值比当前值大 { x=k; //当前值给小的（x） splitv(r[k],w,r[x],y); //向右子树继续分裂 pup(x); } else { y=k; splitv(l[k],w,x,l[y]); pup(y); } } void splits(int k,int w,int &x,int &y) //按个数分裂，保证x<=y,(x就是那前w个) { if(!k) x=y=0; else if(w<=sz[l[k]]) //如果当前个数多余 { y=k; //比w多，一定是在y上的 splits(l[k],w,x,l[y]); //向左子树分裂 pup(y); } else { x=k; splits(r[k],w-sz[l[k]]-1,r[x],y); pup(x); } } void ins(int x) //插入 { int t1,t2; splitv(rt,x,t1,t2); //把一棵树分裂成按x分裂成两部分 rt=hb(hb(t1,xj(x)),t2); //再把左边与x合并，再与右边合并 } void del(int x) //删除 { int a,b,c,d; splitv(rt,x-1,a,b); //把它分成两部分（x是右边那部分的最小值） splits(b,1,c,d); //把右边分裂出一个大小为1的点c（x） rt=hb(a,d); //不管c，直接合并a，d（忽略了一个x） } int askpm(int x) //查x的排名 { int a,b; splitv(rt,x-1,a,b); //裂出所有比x小的数 int ans=sz[a]+1; //x排名为比它小的数的个数+1 rt=hb(a,b); //把树合并回去 return ans; } int askdx(int x) //查第x大的数 { int a,b,c,d; splits(rt,x-1,a,b); //把前x-1个数裂出来 splits(b,1,c,d); //那么没被裂出来的数中的第一个,一定就是第x大的 int ans=v[c]; rt=hb(a,hb(c,d)); //把所有裂开的都依次合回去 return ans; } int askq(int x) //查前驱 { int a,b,c,d; splitv(rt,x-1,a,b); //把比它小的数裂出来 splits(a,sz[a]-1,c,d); //在小的中裂出最大的一个 int ans=v[d]; rt=hb(hb(c,d),b); //合并 return ans; } int askh(int x) //查后继 { int a,b,c,d; splitv(rt,x,a,b); //把比它大的裂出来 splits(b,1,c,d); //在比它大的数中找最小的 int ans=v[c]; rt=hb(a,hb(c,d)); //合并 return ans; } }T; int main() { int t; cin>>t; while(t--) { int opt,x; scanf("%d%d",&opt,&x); if(opt==1) T.ins(x); if(opt==2) T.del(x); if(opt==3) printf("%d\n",T.askpm(x)); if(opt==4) printf("%d\n",T.askdx(x)); if(opt==5) printf("%d\n",T.askq(x)); if(opt==6) printf("%d\n",T.askh(x)); } } ``` 写于2019.12.13,纪念学会fhq 同时纪念南京大屠杀