蒟蒻的FHQ Treap板子求调

#include<cstdio>
#include<iostream>
#include<stdlib.h>
#define int long long
const int N=1e5+10;
int n;
struct Tree{
	int d,siz,L,R,ran;//ran优先性，保证结构不退化 
}t[N];
int tot=0,root=1;
void New(int v)
{
	t[++tot].d=v;
	t[tot].L=t[tot].R=0; 
	t[tot].siz=1;
	t[tot].ran=rand();
}
void pushup(int p)
{
	t[p].siz=t[t[p].L].siz+t[t[p].R].siz+1;
}
void Split(int p,int &l,int &r,int x)
{
	if (!p)
	{
		l=r=0;
		return;
	}
	if (t[p].d<=x)//小于等于放左子树 
	{
		l=p;
		Split(t[p].R,t[p].R,r,x);
	}
	else
	{
		r=p;
		Split(t[p].L,l,t[p].L,x);
	}
	pushup(p);
}
int Merge(int l,int r)//返回根节点 
{
	if (!l||!r) return l+r;
	if (t[l].ran<=t[r].ran)
	{
		t[r].L=Merge(l,t[r].L);
		pushup(r);
		return r;
	}
	else
	{
		t[l].R=Merge(t[l].R,r);
		pushup(l);
		return l;
	}
}
void Insert(int x)
{
	int l,r;
	Split(root,l,r,x);
	New(x);
	int l1=Merge(l,tot);
	root=Merge(l1,r);
}
void Delete(int x)
{
	int l,r,p;
	Split(root,l,r,x);//左儿子带x，右儿子不带 
	Split(l,l,p,x-1);//分出左儿子中的x树 
	p=Merge(t[p].L,t[p].R);//合并x树的左右儿子，相当于删掉根节点 
	root=Merge(Merge(l,p),r);
}
int Rank(int x)//查询数x的排名 
{
	int l,r;
	Split(root,l,r,x-1);//左子树不包括x 
	int k=t[l].siz;
	root=Merge(l,r);
	return k+1;
}
int k_th(int p,int k)//查询排名为k的数
{
	if (t[t[p].L].siz+1==k) return p;//返回的是编号 
	if (t[t[p].L].siz>=k) return k_th(t[p].L,k);//在左子树 
	else return k_th(t[p].R,k-t[t[p].L].siz-1);//在右子树 
}
int pre(int x)//前驱 
{
	int l,r;
	Split(root,l,r,x-1);//左子树最大的是x-1 
	int p=k_th(l,t[l].siz);//查找左子树最大的（最右 
	root=Merge(l,r);
	return p;
} 
int suc(int x)//后继 
{
	int l,r;
	Split(root,l,r,x);//右子树最小的是x+1 
	int p=k_th(r,1);//查询右子树最小的（最左 
	root=Merge(l,r);
	return p;
}
signed main()
{
	scanf("%lld",&n);
	while (n--)
	{
		int op,x;
		scanf("%lld%lld",&op,&x);
		if (op==1) Insert(x);
		else if (op==2) Delete(x);
		else if (op==3) printf("%lld\n",Rank(x));
		else if (op==4) printf("%lld\n",t[k_th(root,x)].d);
		else if (op==5) printf("%lld\n",t[pre(x)].d);
		else printf("%lld\n",t[suc(x)].d);
	}
	return 0;
}