FHQ_Treap

先记个板子

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n; 
int rt,son[N][2],sz[N],va[N],pri[N],tot;
struct FHQ
{
	void pushup(int x) {sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;}
	int merge(int x,int y)
	{
		if(!x||!y) return x|y;
		if(pri[x]<pri[y]) return son[x][1]=merge(son[x][1],y),pushup(x),x;
		else return son[y][0]=merge(x,son[y][0]),pushup(y),y;
	}
	void split(int rt,int k,int &x,int &y)
	{
		if(!rt) return x=y=0,void (0);
		if(va[rt]<=k) x=rt,split(son[rt][1],k,son[rt][1],y);
		else y=rt,split(son[rt][0],k,x,son[rt][0]);
		pushup(rt);
	}
	int kth(int rt,int k){
		if(k<=sz[son[rt][0]])return kth(son[rt][0],k);
		if(k==sz[son[rt][0]]+1)return rt;
		return kth(son[rt][1],k-sz[son[rt][0]]-1);
	}
	int nw(int k) {va[++tot]=k; sz[tot]=1; pri[tot]=rand(); return tot;}
	void ins(int k)
	{
		int x,y;
		split(rt,k,x,y); rt=merge(merge(x,nw(k)),y);
	}
	void del(int k)
	{
		int x,y,z;
		split(rt,k,x,y); split(x,k-1,x,z);
		z=merge(son[z][0],son[z][1]);
		rt=merge(merge(x,z),y);
	}
	int rk(int k)
	{
		int x,y,res; split(rt,k-1,x,y); res=sz[x]+1;
		return rt=merge(x,y),res;
	}
	int pre(int k)
	{
		int x,y,res; split(rt,k-1,x,y);
		int kk=kth(x,sz[x]);
		 res=va[kk];
		return rt=merge(x,y),res;
	}
	int nxt(int k)
	{
		int x,y,res; split(rt,k,x,y); res=va[kth(y,1)];
		return rt=merge(x,y),res;
	}
} tp;

int main()
{
	scanf("%d",&n);
	while(n--)
	{
		int c,x; scanf("%d%d",&c,&x);
		if(c==1) tp.ins(x);
		if(c==2) tp.del(x);
		if(c==3) printf("%d\n",tp.rk(x));
		if(c==4) printf("%d\n",va[tp.kth(rt,x)]);
		if(c==5) printf("%d\n",tp.pre(x));
		if(c==6) printf("%d\n",tp.nxt(x));
	}
	return 0;
}