理解
注意：
k e y key key 键值
f i x fix fix 优先级
合并 int Merge(int u,int v){if(!u||!v) return u+v;if(fix[u]<fix[v]){ch[u][1]=Merge(ch[u][1],v);PushUp(u);return u;}else{ch[v][0]=Merge(u,ch[v][0]);PushUp(v);return v;}}
盗图
注意函数只利用了 f i x fix fix 来进行合并，保证堆性质，这里是大根堆，并且两个树要保证 左 ≤ le ≤ 右
这是一个例子
这是自顶向下的函数
可持久化的时候改变了某些点的父子关系
分裂 void Split(int u,int val,int &x,int &y){if(!u){x=0,y=0;return ;}if(key[u]<=val)x=u,Split(ch[u][1],val,ch[x][1],y);else y=u,Split(ch[u][0],val,x,ch[y][0]);PushUp(u);return ;} void Split(int u,int k,int &x,int &y){if(!u){x=0,y=0;return ;}if(k<=siz[ch[u][0]])y=u,Split(ch[u][0],k,x,ch[y][0]);else x=u,Split(ch[u][1],k-siz[ch[u][0]]-1,ch[x][1],y);PushUp(u);return ;}
盗图
分裂其实有两种，排名分裂和键值分裂
排名分裂一般用于处理序列问题
权值分裂一般用于处理BST问题(不知道怎么说…)
然后所有操作都水了
关于可持久化
Fhq_Treap的可持久化的图并没有主席树那样清晰易懂(如果有插入节点的话)
但是我们的思想始终是自顶向下
所以分裂操作时候每次新建节点即可
比如这个图，这些节点都新建了
代码 //#pragma GCC optimize(2)//#pragma GCC optimize(3)#include<set>#include<map>#include<stack>#include<cmath>#include<ctime>#include<queue>#include<cstdio>#include<vector>#include<climits>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define LL long longusing namespace std;int read(){bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;}#define MAXN 100000#define INF 0x3f3f3f3fnamespace Fhq_Treap{int Root,ncnt;int ch[MAXN+5][2],siz[MAXN+5],key[MAXN+5],fix[MAXN+5];inline void PushUp(int u){siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;return ;}int Newnode(int val){siz[++ncnt]=1,key[ncnt]=val,fix[ncnt]=rand(),ch[ncnt][0]=ch[ncnt][1]=0;return ncnt;}int Merge(int u,int v){if(!u||!v) return u+v;if(fix[u]<fix[v]){ch[u][1]=Merge(ch[u][1],v);PushUp(u);return u;}else{ch[v][0]=Merge(u,ch[v][0]);PushUp(v);return v;}}void Split(int u,int val,int &x,int &y){if(!u){x=0,y=0;return ;}if(key[u]<=val)x=u,Split(ch[u][1],val,ch[x][1],y);else y=u,Split(ch[u][0],val,x,ch[y][0]);PushUp(u);return ;}void Insert(int &rt,int val){int x,y;Split(rt,val,x,y),rt=Merge(Merge(x,Newnode(val)),y);return ;}void Delete(int &rt,int val){int x,y,z;Split(rt,val-1,x,y),Split(y,val,y,z);y=Merge(ch[y][0],ch[y][1]);rt=Merge(Merge(x,y),z);return ;}int GetRank(int &rt,int val){int x,y;Split(rt,val-1,x,y);int ret=siz[x]+1;rt=Merge(x,y);return ret;}int Kth(int u,int k){while(1){if(k<=siz[ch[u][0]]) u=ch[u][0];else if(k==siz[ch[u][0]]+1) break;else k-=siz[ch[u][0]]+1,u=ch[u][1];}return u;}int FindPre(int &rt,int val){int x,y;Split(rt,val-1,x,y);int ret=key[Kth(x,siz[x])];rt=Merge(x,y);return ret;}int FindNxt(int &rt,int val){int x,y;Split(rt,val,x,y);int ret=key[Kth(y,1)];rt=Merge(x,y);return ret;}}using namespace Fhq_Treap;/*插入x 删除x 查x排名 查排名为x x前驱 x后继*/int main(){srand(time(NULL));int T=read();while(T--){int opt=read(),x=read();if(opt==1) Insert(Root,x);if(opt==2) Delete(Root,x);if(opt==3) printf("%dn",GetRank(Root,x));if(opt==4) printf("%dn",key[Kth(Root,x)]);if(opt==5) printf("%dn",FindPre(Root,x));if(opt==6) printf("%dn",FindNxt(Root,x));}return 0;}