可持久化（普通）平衡树

#include<iostream>
#include<random>

using namespace std;

const int N=5e5+5,INF=0x7fffffff;
mt19937 Rand(time(0));
struct node{
	node *l,*r;
	int val,siz,pri;
	
	node(int v): l(nullptr),r(nullptr),val(v),siz(1),pri(Rand()){}
	void pushup(){
		siz=1;
		if(l!=nullptr) siz+=l->siz;
		if(r!=nullptr) siz+=r->siz;
	}
};
node *rt[N];
struct FHQ_treap{
	node *clone(node *u){
		if(u==nullptr) return nullptr;
		auto tmp=new node(u->val);
		tmp->l=u->l;
		tmp->r=u->r;
		tmp->siz=u->siz;
		tmp->pri=u->pri;
		return tmp;
	}
	int getsiz(node *u){
		if(u==nullptr) return 0;
		return u->siz;
	}
	void split(node *u,int val,node *&x,node *&y){
		if(u==nullptr){
			x=y=nullptr;
			return ;
		}
		if(u->val<=val){
			x=clone(u);
			split(u->r,val,x->r,y);
			x->pushup();
		}
		else{
			y=clone(u);
			split(u->l,val,x,y->l);
			y->pushup();
		}
	}
	node *merge(node *u,node *v){
		if(u==nullptr) return v;
		if(v==nullptr) return u;
		if(u->pri>v->pri){
			u->r=merge(u->r,v);
			u->pushup();
			return u;
		}
		else{
			v->l=merge(u,v->l);
			v->pushup();
			return v;
		}
	}
	void insert(node *&u,int val){
		node *ltr,*rtr;
		split(u,val,ltr,rtr);
		u=merge(merge(ltr,new node(val)),rtr);
	}
	void erase(node *&u,int pos){
		node *ltr,*rtr,*mid;
		split(u,pos,mid,rtr);
		split(mid,pos-1,ltr,mid);
		if(mid!=nullptr) mid=merge(mid->l,mid->r);
		u=merge(merge(ltr,mid),rtr);
	}
	int queryrank(node *u,int val){
		node *ltr,*rtr;
		split(u,val-1,ltr,rtr);
		int res=getsiz(ltr)+1;
		u=merge(ltr,rtr);
		return res;
	}
	node *queryval(node *u,int rnk){
		auto pos=u;
		while(pos!=nullptr){
			int lsiz=getsiz(pos->l);
			if(rnk==lsiz+1) return pos;
			if(rnk<lsiz+1) pos=pos->l;
			else{
				rnk-=lsiz+1;
				pos=pos->r;
			}
		}
		return pos;
	}
	node *getpre(node *u,int val){
		node *ltr,*rtr;
		split(u,val-1,ltr,rtr);
		while(ltr!=nullptr && ltr->r!=nullptr) ltr=ltr->r;
		return ltr;
	}
	node *getnext(node *u,int val){
		node *ltr,*rtr;
		split(u,val,ltr,rtr);
		while(rtr!=nullptr && rtr->l!=nullptr) rtr=rtr->l;
		return rtr;
	}
};
FHQ_treap tr;

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin>>n;
	rt[0]=nullptr;
	for(int i=1;i<=n;i++){
		int v,opt,x;
		cin>>v>>opt>>x;
		rt[i]=rt[v];
		if(opt==1) tr.insert(rt[i],x);
		if(opt==2) tr.erase(rt[i],x);
		if(opt==3) cout<<tr.queryrank(rt[i],x)<<'\n';
		if(opt==4) cout<<tr.queryval(rt[i],x)->val<<'\n';
		if(opt==5){
			auto tmp=tr.getpre(rt[i],x);
			if(tmp==nullptr) cout<<-INF<<'\n';
			else cout<<tmp->val<<'\n';
		}
		if(opt==6){
			auto tmp=tr.getnext(rt[i],x);
			if(tmp==nullptr) cout<<INF<<'\n';
			else cout<<tmp->val<<'\n';
		}
	}
}