RT。有 WA,TLE,MLE,AC。用的FHQ-Treap，救救孩子吧 OvO

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,INF=1e9;
int tot,Root,T;
struct Treap{
	int val,siz,pri;
	int lc,rc;
}a[N];
void pushup(int cur){
	a[cur].siz=a[a[cur].lc].siz+a[a[cur].rc].siz+1;
	return;
}
void split(int rt,int k,int &x,int &y){
	if(!rt){
		x=y=0;
		return;
	}
	if(k<=a[a[rt].lc].siz){
		split(a[rt].lc,k,x,y);
		a[rt].lc=y;
		pushup(rt);
		y=rt;
	}
	else{
		split(a[rt].rc,k-a[a[rt].lc].siz-1,x,y);
		a[rt].rc=x;
		pushup(rt);
		x=rt;
	}
	return;
}
int merge(int x,int y){
	if(!x||!y)
		return x+y;
	if(a[x].pri<a[y].pri){
		a[x].rc=merge(a[x].rc,y);
		pushup(x);
		return x;
	}
	else{
		a[y].lc=merge(x,a[y].lc);
		pushup(y);
		return y;
	}
}
int Rank(int rt,int val){
	if(!rt)
		return 0;
	if(val<a[rt].val)
		return Rank(a[rt].lc,val);
	else
		return Rank(a[rt].rc,val)+a[a[rt].lc].siz+1;
}
void insert(int val){
	a[++tot].val=val,a[tot].pri=rand()%INF;
	a[tot].lc=a[tot].rc=0;
	a[tot].siz=1;
	int rk=Rank(Root,val);
	int x,y;
	split(Root,rk,x,y);
	Root=merge(merge(x,tot),y);
	return;
}
void delet(int val){
	int rk=Rank(Root,val);
	int obs,x,y,tmp;
	split(Root,rk,obs,y);
	split(Root,rk-1,x,tmp);
	Root=merge(x,y);
	return;
}
int getnum(int k){
	int x,y,z,num;
	split(Root,k,x,y);
	split(x,k-1,z,num);
	Root=merge(z,merge(num,y));
	return a[num].val;
}
signed main(){
	srand(time(0));
	cin>>T;
	while(T--){
		int op,x;
		cin>>op>>x;
		if(op==1)
			insert(x);
		else if(op==2)
			delet(x);
		else if(op==3)
			cout<<Rank(Root,x)<<"\n";
		else if(op==4)
			cout<<getnum(x)<<"\n";
		else if(op==5)
			cout<<getnum(Rank(Root,x-1))<<"\n";
		else
			cout<<getnum(Rank(Root,x)+1)<<"\n";
	}
	return 0;
}