前言
好久没码过平衡树了！
这次在闪指导的指导下学会了\(FHQ\ Treap\)，一方面是因为听说它可以可持久化，另一方面则是因为听说它是真的好写。
简介
\(FHQ\ Treap\)，又称作非旋\(Treap\)。
其实在我看来，它与\(Treap\)的共同点也只有都借助了随机键值来维护平衡。
具体实现起来，两者真是大为不同。
不过，为助于理解，还是在这里贴上\(Treap\)的博客吧：简析平衡树（二）——Treap。
\(FHQ\ Treap\)的核心操作
其他内容我也就不多说了，下面就从\(FHQ\ Treap\)的两个核心操作讲起吧。
核心操作\(1\)：\(Merge\)
\(Merge\)，即为合并，感觉与线段树、左偏树等数据结构的合并有些神似。
首先我们判断当前合并的两个节点中是否有空节点，有就直接返回。
然后，我们比较二者键值大小，让键值大的作为当前节点，并递归合并其子节点和键值小的节点。
代码如下：
I void Merge(int& k,RI x,RI y)//合并x和y，存储到k，其中x中的元素小于等于y中的元素
{
if(!x||!y) return (void)(k=x+y);//如果有空节点，直接返回
O[x].D>O[y].D?(k=x,Merge(SX)):(k=y,Merge(SY)),PU(k);//比较键值，递归合并
}
核心操作\(2\)：\(Split\)操作
\(Split\)，即为分裂，这是一些普通平衡树没有的操作。
与\(Merge\)类似，因为它本来就是\(Merge\)的逆操作。
这里的分裂是按照一定标准进行分裂的，这里以按权值大小分裂为例。
首先我们判断当前分裂的节点是否为空节点，是则直接返回。
然后，若当前权值小于等于分裂权值，存到第一棵树中，否则存到第二棵树中。
代码如下：
I void Split(RI k,int& x,int& y,CI v)//分裂k，存储到x和y，其中小于等于v的元素存储到x，大于v的元素存储到y
{
if(!k) return (void)(x=y=0);//如果当前分裂节点为空，直接返回
O[k].V<=v?(x=k,Split(SX,v)):(y=k,Split(SY,v)),PU(k);//按权值分裂，递归继续分裂
}
其他操作
其他操作主要使用的就是\(Merge\)和\(Split\)两个操作，因此下面就不多加介绍了。
完整代码（板子题）
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
using namespace std;
int n;
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int f,T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
#undef D
}F;
class FHQTreap //FHQ Treap模板
{
private:
#define Rd() (seed=(233333LL*seed+666667)%2147483648LL)//手写随机数
#define SX O[k].S[1],O[x].S[1],y
#define SY O[k].S[0],x,O[y].S[0]
#define NewNode(v) (O[++tot].Sz=1,O[tot].V=v,O[tot].D=Rd(),tot)//建立新节点
#define PU(x) (O[x].Sz=O[O[x].S[0]].Sz+O[O[x].S[1]].Sz+1)//上传信息
int rt,tot,seed;struct node {int Sz,V,D,S[2];}O[N+5];
I void Merge(int& k,RI x,RI y)//合并x和y，存储到k，其中x中的元素小于等于y中的元素
{
if(!x||!y) return (void)(k=x+y);//如果有空节点，直接返回
O[x].D>O[y].D?(k=x,Merge(SX)):(k=y,Merge(SY)),PU(k);//比较键值，递归合并
}
I void Split(RI k,int& x,int& y,CI v)//分裂k，存储到x和y，其中小于等于v的元素存储到x，大于v的元素存储到y
{
if(!k) return (void)(x=y=0);//如果当前分裂节点为空，直接返回
O[k].V<=v?(x=k,Split(SX,v)):(y=k,Split(SY,v)),PU(k);//按权值分裂，递归继续分裂
}
I int Find(RI k,RI rk)//找到k子树内排名为rk的点
{
W((O[O[k].S[0]].Sz+1)^rk) O[O[k].S[0]].Sz>=rk? //如果在左子树中
k=O[k].S[0]:(rk-=O[O[k].S[0]].Sz+1,k=O[k].S[1]);//否则在右子树中
return k;//返回答案
}
public:
I FHQTreap() {seed=20050521;}//初始化随机种子
I void Insert(CI v)//插入元素
{
RI x=0,y=0,k=NewNode(v);//新建一个权值为当前插入值的点
Split(rt,x,y,v),Merge(x,x,k),Merge(rt,x,y);//分裂为小于等于v和大于v的两棵树，然后依次合并
}
I void Delete(CI v)//删除元素
{
RI x=0,y=0,k=0;Split(rt,x,y,v),Split(x,x,k,v-1),//先通过两次合并，此时k子树中值全为v
Merge(k,O[k].S[0],O[k].S[1]),Merge(x,x,k),Merge(rt,x,y);//合并k的两个子节点（即删除k的根节点），然后依次合并
}
I int GetRk(CI v) {RI x=0,y=0,k;return Split(rt,x,y,v-1),k=O[x].Sz+1,Merge(rt,x,y),k;}//求给定值的排名，分裂出小于v的树，其Size+1即为v的排名
I int GetVal(CI v) {return O[Find(rt,v)].V;}//求给定排名的值，直接调用Find()函数
I int GetPre(CI v) {RI x=0,y=0,k;return Split(rt,x,y,v-1),k=Find(x,O[x].Sz),Merge(rt,x,y),O[k].V;}//求前驱，分裂出小于v的树，其中最大的值即为v的前驱
I int GetNxt(CI v) {RI x=0,y=0,k;return Split(rt,x,y,v),k=Find(y,1),Merge(rt,x,y),O[k].V;}//求后继，分裂出大于v的树，其中最小的值即为v的后继
}T;
int main()
{
RI Qt,op,x;F.read(Qt);W(Qt--) switch(F.read(op,x),op)
{
case 1:T.Insert(x);break;//插入元素
case 2:T.Delete(x);break;//删除元素
case 3:F.writeln(T.GetRk(x));break;//求给定值的排名
case 4:F.writeln(T.GetVal(x));break;//求给定排名的值
case 5:F.writeln(T.GetPre(x));break;//求前驱
case 6:F.writeln(T.GetNxt(x));break;//求后继
}return F.clear(),0;
}