本文内容粗略，不适合新手阅读
但如果你已经进来了，推荐你到这里学习
当然是写给我复习用
fhq-treap通过分裂和合并连个操作，以临界值分离二叉搜索树
由于在合并时引进可了随机数，使其平衡性得到保障
结构体
struct node{int ls,rs,val,p,s;//分别为左儿子，右儿子，该节点存的值，随机数（用于合并），以该节点为根的子树的大小
};
分离
void split(int u,int x,int& l,int& r){//u当前节点，x临界值，l在值域为1到x之间的树接下来需要添加节点的位置，r与l同理，值域在x+1到m之间if(u==0){//如果u节点时不存在的，这里不需要添加，l和r指向0，以该节点为根的子树大小l=r=0;return;}if(t[u].val<=x){//当前节点的值比x小，因为以其左节点为根的子树的值均小于该节点的值，所以将左子树和当前节点给l,右子树继续分离l=u;split(t[u].rs,x,t[u].rs,r);}else{//与上同理r=u;split(t[u].ls,x,l,t[u].ls);}push_up(u);//更新节点大小
}
合并
合并时，并不能确定哪个点作为根，如果只选左或只选右或诸如此类有规律性的选法，很有可能使平衡树退化
所以引入随机数，随机数p值较大的优先作为根节点
//调用merge的条件：u点的val小于等于v点的val
int merge(int u,int v){//返回merge后的根节点if(!u||!v) return u|v;if(t[u].p>t[v].p){//u为根节点t[u].rs=merge(t[u].rs,v);//注意顺序push_up(u);return u;}else{//v为根节点t[v].ls=merge(u,t[v].ls);//注意顺序push_up(v);return v;}
}
模板
然后就可以通过merge和split进行各种操作了
过程中维护一个根节点即可
放个我自己写的模板
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=x*10+c-48;x=(f ? -x : x);return;
}
mt19937 rd(time(NULL));
struct node{int ls,rs,val,p,s;
};
int node_cnt=0,rt;
node t[maxn];
int new_node(int x){++node_cnt;t[node_cnt]=(node){0,0,x,(int)rd(),1};return node_cnt;
}
void push_up(int u){t[u].s=t[t[u].ls].s+t[t[u].rs].s+1;
}
void split(int u,int x,int& l,int& r){if(u==0){l=r=0;return;}if(t[u].val<=x){l=u;split(t[u].rs,x,t[u].rs,r);}else{r=u;split(t[u].ls,x,l,t[u].ls);}push_up(u);
}
int merge(int u,int v){if(!u||!v) return u|v;if(t[u].p>t[v].p){t[u].rs=merge(t[u].rs,v);push_up(u);return u;}else{t[v].ls=merge(u,t[v].ls);push_up(v);return v;}
}
void insert(int x){int u,v;split(rt,x,u,v);int p=new_node(x);rt=merge(merge(u,p),v);
}
void remove(int x){int u,v,w;split(rt,x,u,v);split(u,x-1,u,w);w=merge(t[w].ls,t[w].rs);rt=merge(merge(u,w),v);
}
int rnk(int x){int u,v;split(rt,x-1,u,v);int ans=t[u].s+1;rt=merge(u,v);return ans;
}
int kth(int x,int u=rt){int i=t[t[u].ls].s+1;if(i==x) return t[u].val;else if(x<i) return kth(x,t[u].ls);else return kth(x-i,t[u].rs);
}
int pre(int x){int u,v;split(rt,x-1,u,v);int ans=kth(t[u].s,u);rt=merge(u,v);return ans;
}
int nxt(int x){int u,v;split(rt,x,u,v);int ans=kth(1,v);rt=merge(u,v);return ans;
}
int q;
int main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);read(q);int op,x;while(q--){read(op),read(x);if(op==1) insert(x);else if(op==2) remove(x);else if(op==3) printf("%d\n",rnk(x));else if(op==4) printf("%d\n",kth(x));else if(op==5) printf("%d\n",pre(x));else printf("%d\n",nxt(x));}return 0;
}
//^o^