题解 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大小
(简单来说,你可以理解为让小的合并到大的的概率更大)
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树上
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树上
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合并即为所求
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
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进行,也可以用分裂合并,读者自想不难,想不出的可以看代码,注释里说的很详细
代码:
#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
同时纪念南京大屠杀