众所周知,FHQ-Treap是一个码量少,可区间翻转,能持久化的treap(只是常熟略大)像我这种蒟蒻,想调处有旋Treap或者Splay肯定要个114514年
以下可能以FHQ代表FHQ-Treap(逃
treap的节点拥有两个权值,一个是值,一个是优先级。优先级满足堆的性质,值满足二叉搜索树的性质。当两个权值相同时,treap是固定的。堆的性质以及随机的优先级可以让树深保持在\(\log n\),确保时间复杂度;而二叉搜索树可以带来求排名,前驱,后继等操作。
(相关资料图)
FHQ-Treap 的合并要求一个FHQ的值全部小于等于另一个,建议是确定一下哪个大,哪个小。这里以左小右大为例.
这个就是和线段树一模一样的Update,不保熟(
void Update(int pos){siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;}
siz即FHQ的大小,son[pos][0]代表左儿子,son[pos][1]代表右儿子
字面意思,将一个FHQ按权值\(val\)分成小于等于和大于两个。我们将一个FHQ分成\(x\)、\(y\)两个(即根节点为\(x\)、\(y\))本文中左(即\(x\)FHQ)一律小于右(即\(y\)FHQ)
假设我们在原FHQ的节点\(pos\)
若该点的值大于\(val\)由二叉搜索树可知该点和它的右子树节点都大于\(val\),将其置入右(y)FHQ并在左子树中寻找也大于\(val\)的子树,归入该点在\(y\)FHQ所在点的左子树中
若该点的值小于等于\(val\)由二叉搜索树可知该点和它的左子树节点都小于等于\(val\),将其置入左(x)FHQ并在右子树中寻找也小于等于\(val\)的子树,归入该点在\(x\)FHQ所在点的右子树中(可能有点绕)回溯时记得及时在该点Update以保证子树大小正确。
若\(pos\)为0,即空子树,便无法再分
void Split(int pos,int vlx,int &x,int &y){if(pos==0){x=y=0;return;}if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);Update(pos);}
将两个FHQ合并,要求一个FHQ的所有值都小于等于另一个。由于值都是已经有大小的,我们可以将\(x\)置入\(y\)的左子树或将\(y\)置入\(x\)的右子树但我们要使优先级满足堆的性质
再次假设我们在两个FHQ的节点\(x\)和\(y\) 这里以小根堆为例
若\(x\)的优先级大于\(y\)优先级,由堆可知\(x\)和它的子树节点的优先级都大于\(y\)的优先级,因为\(x\)的值小于等于\(y\),将其加在\(y\)的左子树下
若\(x\)的优先级小于\(y\)优先级,由堆可知\(y\)和它的子树节点的优先级都大于\(x\)的优先级,因为\(y\)的值大于\(y\),将其加在\(x\)的右子树下
这里等于的条件归在哪都无所谓
回溯时记得及时在该点Update以保证子树大小正确。
若\(x\),\(y\)有一个或多个为0,即存在空节点,直接返回另一个节点或0即可
int Merge(int x,int y){if(x==0||y==0)return x+y;if(rnd[x]>rnd[y]){son[y][0]=Merge(x,son[y][0]),Update(y); return y;}else{son[x][1]=Merge(son[x][1],y),Update(x); return x;}}
获得排名为\(vlx\)的树本文将相同的点归在同一点,使用cnt记录其实也可当作不同的点只需修改下Get和插入这里其实和不同的BST一样若\(vlx\)小于等于左子树大小,则进入左子树若\(vlx\)大于左子树大小+该节点个数(即总个数-右子树大小),则减去左子树大小和该点的cnt,进入右子树若\(vlx\)大于左子树大小且小于等于左子树大小+该节点个数,该排名就是该节点的值,return即可
int Get(int pos,int vlx){if(vlxsiz[son[pos][0]]+cnt[pos])return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);return val[pos];}
以上的方法都是\(O(log n)\)的,每次都是进入左子树或右子树,总共不超过\(log n\)层
要插入\(vlx\)值现将原FHQ分裂出小于等于\(vlx\)的\(x\)和大于的\(y\)再从\(x\)中分出小于等于\(vlx\)的\(x"\)和等于\(vlx\)的\(z\)若\(z\)存在,给节点\(z\)的副本数和大小都加1不存在,则新建一个\(z\)节点再按顺序Merge回去
Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(z==0) New(z,vlx);else cnt[z]++,siz[z]++;Root=Merge(Merge(x,z),y);
说道删除,FHQ直接呵呵嗨只需按插入的方法分出\(x\)若\(z\)存在且副本数大于一,给节点\(z\)的副本数和大小都减1若副本数等于一,直接丢到垃圾桶里(若\(z\)不存在,???删不存在的数???
Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(cnt[z]>1) cnt[z]--,siz[z]--;else z=0;Root=Merge(Merge(x,z),y);
按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ答案即是\(x\)大小加1
Split(Root,vlx-1,x,y);write(siz[x]+1),pc("\n");Root=Merge(x,y);
调用Get即可
write(Get(Root,vlx)),pc("\n");
按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ\(x\)中的最大值及是x中排名做后的Get出\(x\)中排名为\(siz[x]\)的即可
Split(Root,vlx-1,x,y);write(Get(x,siz[x])),pc("\n");Root=Merge(x,y);
按\(vlx\)分裂出大于\(vlx\)的\(y\)FHQ\(y\)中的最小值及是y中排名第一的Get出\(x\)中排名为1的即可
Split(Root,vlx,x,y);write(Get(y,1)),pc("\n");Root=Merge(x,y);
附上完整代码
#include#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define Ts template#define Tp template#define ll long long#define RS register#define gc getchar#define pc putchar#define I inlineusing namespace std;Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}namespace WrongIO{Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!="-")c=gc();if(c=="-")opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-"0",c=gc();x*=opt;return;}Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc("0");else pc("-"),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+"0");return;} I void writec(char c[]){int len=strlen(c);for(int i=0;ir)) c=gc();} I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();} I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();} I void readls(string &s){char c=gc();while(c!="\n") s.push_back(c),c=gc();} Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}} using namespace WrongIO;int val[100050],cnt[100050],rnd[100050],siz[100050],son[100050][2],ct;int n,Root;void Update(int pos){siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;}void New(int &id,int vlx){id=++ct;val[id]=vlx;rnd[id]=rand();siz[id]=cnt[id]=1;return;}int Merge(int x,int y){if(x==0||y==0)return x+y;if(rnd[x]>rnd[y]){son[y][0]=Merge(x,son[y][0]),Update(y); return y;}else{son[x][1]=Merge(son[x][1],y),Update(x); return x;}}void Split(int pos,int vlx,int &x,int &y){if(pos==0){x=y=0;return;}if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);Update(pos);}int Get(int pos,int vlx){if(vlxsiz[son[pos][0]]+cnt[pos])return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);return val[pos];}int main(){//fo("input5");read(n);for(int i=1;i<=n;i++){int opt,vlx,x,y,z; read(opt,vlx);if(opt==1){Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(z==0) New(z,vlx);else cnt[z]++,siz[z]++;Root=Merge(Merge(x,z),y);}if(opt==2){Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(cnt[z]>1) cnt[z]--,siz[z]--;else z=0;Root=Merge(Merge(x,z),y);}if(opt==3){Split(Root,vlx-1,x,y);write(siz[x]+1),pc("\n");Root=Merge(x,y);}if(opt==4){write(Get(Root,vlx)),pc("\n");}if(opt==5){Split(Root,vlx-1,x,y);write(Get(x,siz[x])),pc("\n");Root=Merge(x,y);}if(opt==6){Split(Root,vlx,x,y);write(Get(y,1)),pc("\n");Root=Merge(x,y);}} return 0;}//555,卡芙卡的池子歪了一个最不想要的姬子
1、FHQ-Treap真的短,好多都压成了一行写,导致Merge函数,忘写返回值了(2、若将相同点合成一个点,在副本数加1的同时一定要给大小也加1,这个更新不到,减1同理3、一定要明确两个FHQ的大小关系,不然会有奇怪的事发生4、分裂中的两个分支容易写错,可能会出现死循环或导致死循环,发生MLE或TLE5、一些地方要以值-1来分裂,要注意6、Merge和Split在pos为0时记得退出7-113、留给评论区114、宇宙射线照射导致的UKE,雄氏老方也治不了(
标签:
Copyright © 2015-2022 亚洲兽药网版权所有 备案号:京ICP备2021034106号-51 联系邮箱:5 516 538 @qq.com