众所周知，FHQ-Treap是一个码量少，可区间翻转，能持久化的treap（只是常熟略大）
像我这种蒟蒻，想调处有旋Treap或者Splay肯定要个114514年
以下可能以FHQ代表FHQ-Treap（逃
前置芝士
treap的节点拥有两个权值，一个是值，一个是优先级。优先级满足堆的性质，值满足二叉搜索树的性质。
当两个权值相同时，treap是固定的。堆的性质以及随机的优先级可以让树深保持在\(\log n\)，确保时间复杂度；而二叉搜索树可以带来求排名，前驱，后继等操作。
前置提醒
FHQ-Treap 的合并要求一个FHQ的值全部小于等于另一个，建议是确定一下哪个大，哪个小。这里以左小右大为例.
操作
1、Update
这个就是和线段树一模一样的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]代表右儿子
2、Split
字面意思，将一个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);
}
3、Merge
将两个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;
}
}
4、Get
获得排名为\(vlx\)的树
本文将相同的点归在同一点，使用cnt记录
其实也可当作不同的点只需修改下Get和插入
这里其实和不同的BST一样
若\(vlx\)小于等于左子树大小，则进入左子树
若\(vlx\)大于左子树大小+该节点个数（即总个数-右子树大小），则减去左子树大小和该点的cnt，进入右子树
若\(vlx\)大于左子树大小且小于等于左子树大小+该节点个数，该排名就是该节点的值，return即可
int Get(int pos,int vlx)
{
if(vlx<siz[son[pos][0]]+1) return Get(son[pos][0],vlx);
if(vlx>siz[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\)层
接下来是不用递归的功能
1、插入
要插入\(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);
2、删除
说道删除，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);
3、查排名
按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ
答案即是\(x\)大小加1
Split(Root,vlx-1,x,y);
write(siz[x]+1),pc('\n');
Root=Merge(x,y);
4、查排名对应的树
调用Get即可
write(Get(Root,vlx)),pc('\n');
5、前驱
按\(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);
6、后继
按\(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<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using 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;i<len;i++)pc(c[i]);}
I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) 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(vlx<siz[son[pos][0]]+1) return Get(son[pos][0],vlx);
if(vlx>siz[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或TLE
5、一些地方要以值-1来分裂，要注意
6、Merge和Split在pos为0时记得退出
7-113、留给评论区
114、宇宙射线照射导致的UKE，雄氏老方也治不了（