本文主要是介绍FHQ Treap模版（luogu P3369），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
FHQ Treap模版（自用），带注释
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;int n,root,idx;struct node{int l,r;int val,key,size;
}tr[N];int getnew(int v){tr[++idx].val=v;//权值tr[idx].key=rand();//堆的随机值tr[idx].size=1;return idx;
}void pushup(int u){tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;//更新大小，一定不要忘了+1
}void split(int u,int v,int &x,int &y){//按值分裂if(!u){x=y=0;return;}if(tr[u].val<=v){//u的左子树全部满足<=v，所以去判断右子树x=u;split(tr[x].r,v,tr[x].r,y);pushup(x);}else{//原理同上y=u;split(tr[y].l,v,x,tr[y].l);pushup(y);}
}int merge(int x,int y){//满足x中所有节点val值小于y中val值if(!x||!y) return x+y;if(tr[x].key<tr[y].key){//合并操作按key值，注意tr[x].r=merge(tr[x].r,y);//把权值小的放在上面，满足堆的性质pushup(x);return x;}else{tr[y].l=merge(x,tr[y].l);pushup(y);return y;}
}void insert(int v){int x,y,z;split(root,v,x,y);z=getnew(v);root=merge(merge(x,z),y);
}void del(int v){int x,y,z;split(root,v,x,z);split(x,v-1,x,y);//最终的y节点权值全部为vy=merge(tr[y].l,tr[y].r);//删除一个值为v的节点root=merge(merge(x,y),z);
}int getrank(int v){//查询v的排名int x,y;split(root,v-1,x,y);int ans=tr[x].size+1;root=merge(x,y);//分裂完别忘了合并return ans;
}int getval(int u,int k){//查询排名为k的数if(k==tr[tr[u].l].size+1) return tr[u].val;//类似二分查找的方式else if(k<=tr[tr[u].l].size) return getval(tr[u].l,k);else return getval(tr[u].r,k-tr[tr[u].l].size-1);
}int getpre(int v){//查询v的前驱int x,y;split(root,v-1,x,y);int ans=getval(x,tr[x].size);root=merge(x,y);return ans;
}int getnxt(int v){int x,y;split(root,v,x,y);int ans=getval(y,1);root=merge(x,y);return ans;
}int main(){scanf("%d",&n);while(n--){int opt,x;scanf("%d %d",&opt,&x);if(opt==1) insert(x);else if(opt==2) del(x);else if(opt==3) printf("%d\n",getrank(x));else if(opt==4) printf("%d\n",getval(root,x));else if(opt==5) printf("%d\n",getpre(x));else printf("%d\n",getnxt(x));}return 0;
}这篇关于FHQ Treap模版（luogu P3369）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
