Problem’s Website
Solution
没错,又是这道题。
再上一篇题解中,我们介绍了使用Treap的做法,那么本篇题解讲解一下fhq−Treap的做法。
先来普及一下,fhq−Treap由OI界的著名DALAO范浩强发明,至于他有多巨,看图吧。
他不仅OI强,人其实也挺 handsome 的。
P.s.该图片来源毕业季 | 范浩强:游走在学业和科研间的清华创客
好了,我们步入正题。
fhq−Treap又叫无旋Treap,顾名思义,就是没有旋转的Treap,取而代之的是分裂和合并,正因如此,fhq−Treap可以解决Treap解决不了的区间问题,而且还可以持久化,这些内容以后我会另外介绍。
首先,我们先明确下文中代码变量的意思。
1 | int siz[Maxn], val[Maxn], dat[Maxn], ch[Maxn][2]; |
在说明基本操作前,我们先来说一下fhq−Treap的一些核心思想及操作
- 分裂
分裂分为两种,一种为权值分裂,另一种为排名分裂。
权值分裂
我们现在遍历到一个点,如果它的权值小于v,那么它的左子树会被分到左边的树里,然后我们遍历它的右儿子,如果大于v,则把它的右子树分到右边的树里。
那出现了一个小问题:如果到达递归边界id==0怎么办呢?
那我们就初始化一下,令x=y=0
如果遍历到了叶子节点,我们就返回。
注意,对于形参中的x,y要取地址,这样就可以直接更新全局变量x,y。
看下代码吧
1 | inline void split(int id, int v, int &x, int &y) { |
排名分裂
与权值分裂类似,把权值当成排名(siz)即可。
code
1 | inline void split(int id, int r, int &x, int &y) { |
给个图感性理解一下:
- 合并
我们假设第一棵树的权值小于第二棵树的权值,那么我们就比较它们的随机权值。如果dat[l]<dat[r],我们就保留它的左子树,另一棵树作为它的右子树;如果dat[l]≥dat[r],那我们可以保留第二棵树的右子树,另一颗树作为它的左子树。
code
1 | inline int merge(int A, int B) { |
图示
现在我们开始介绍fhq−Treap的一些基本操作。
- pushup
合并子树大小。
code
1 | inline void pushup(int id) { |
- 插入
直接merge即可
code
1 | inline int cre(int v) { |
- 删除
删除权值为v的点,先把整颗树以v为权值分裂成两棵树a,b,再把a树按照v−1分成c,d。这时候值为v的点一定为d的根,那么我们把d的两个子儿子merge起来(划重点:这一步就是去除掉v的影响),再把他们重新merge起来得到一个新的树,这颗树就去除掉了v的影响。
code
1 | inline void Delete(int v) { |
- 得到排名
直接按照v−1的权值把树分开,那么x树中最大的应该小于等于v−1,那么v的排名就是siz[x]+1。
code
1 | inline int get_rank(int v) { |
- 得到排名为几的数据
循环求解。
如果当前r≤左子树的大小,那么就往左子树找;如果r恰好等于左子树大小+ 1,说明就是当前节点;否则r减去(左子树大小 + 1),然后去找右子树。
code
1 | inline int rank(int id, int r) { |
- 前驱后驱
因为两者具有很大的相似性,所以我们只讲找前驱,后驱请读者根据代码自行理解。
因为要小于v,所以我们还是按照v−1的权值划分x,现在x中最大的数一定小于等于v−1,所以我们直接输出x中最大的数就好。
code
1 | inline int get_pre(int v) { //前驱 |
本题的操作就讲完了,当然fhq−Treap不止这些东西,以后根据题目再说明吧。
Code
1 |
|
rp++
Gitalking ...