不要问我为什么写的是替罪羊树

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+114;
mt19937_64 rnd(time(0));
double alpha=0.7+rnd()*(0.1/UINT64_MAX);
struct Phs{
	int ls,rs,v,cnt,sz,sz_;
}a[N*100];
inline int new_Phs(){static int p=0;return ++p;}
inline int new_Phs(int v){int i=new_Phs();a[i].v=v,a[i].cnt=1,a[i].sz=1,a[i].sz_=1;return i;}
inline int new_Phs(Phs& t){int i=new_Phs();a[i]=t;return i;}
inline void push_up(int i){
	a[i].sz=a[a[i].ls].sz+a[a[i].rs].sz+a[i].cnt;
	a[i].sz_=a[a[i].ls].sz_+a[a[i].rs].sz_+1;
}
int re[N],rel;
inline bool is_re(int i){
	return a[a[i].ls].sz_>=a[i].sz_*alpha || a[a[i].rs].sz_>=a[i].sz_*alpha;
}
void dfs(int i){
	if(a[i].ls) dfs(a[i].ls);
	re[++rel]=i;
	if(a[i].rs) dfs(a[i].rs);
}
int build(int l,int r){
	if(l>r) return 0;
	int mid=l+r>>1,i=new_Phs(a[re[mid]]);
	a[i].ls=build(l,mid-1),a[i].rs=build(mid+1,r);
	push_up(i);
	return i;
}
int rebuild(int i){
//	cout << "QwQ" << endl;
	rel=0;
//	cout << "QwQ2" << endl;
	dfs(i);
//	cout << "QwQ3" << endl;
	return build(1,rel);
}
void change(int i,int x,int d){
//	cout << i << " " << a[i].v << " " << x << " " << d << endl;
	if(x<a[i].v){
		if(a[i].ls) change(a[i].ls=new_Phs(a[a[i].ls]),x,d);
		else a[i].ls=new_Phs(x);
	}
	else if(x==a[i].v) a[i].cnt=max(a[i].cnt+d,0);
	else{
		if(a[i].rs) change(a[i].rs=new_Phs(a[a[i].rs]),x,d);
		else a[i].rs=new_Phs(x);
	}
	push_up(i);
//	if(a[i].ls && is_re(a[i].ls)) a[i].ls=rebuild(a[i].ls);
//	if(a[i].rs && is_re(a[i].rs)) a[i].rs=rebuild(a[i].rs);
}
int getrk(int i,int x){
	if(x<=a[i].v) return a[i].ls?getrk(a[i].ls,x):0;
	return a[a[i].ls].sz+a[i].cnt+(a[i].rs?getrk(a[i].rs,x):0);
}
int getkth(int i,int rk){
//	cout << a[i].v << " " << rk << endl;
//	if(i==0) exit(0);
	if(rk<a[a[i].ls].sz) return getkth(a[i].ls,rk);
	if(rk<a[a[i].ls].sz+a[i].cnt) return a[i].v;
	return getkth(a[i].rs,rk-a[a[i].ls].sz-a[i].cnt);
}
int rt[N],q;
int main(){
//	cout << alpha << endl;
//	alpha=0.6;
	rt[0]=new_Phs(-2147483647);
	change(rt[0],2147483647,1);
	scanf("%d",&q);
	for(int qwq=1;qwq<=q;++qwq){
		int v,op,x;
		scanf("%d%d%d",&v,&op,&x);
		rt[qwq]=new_Phs(a[rt[v]]);
		if(op==1) change(rt[qwq],x,1);
		else if(op==2) change(rt[qwq],x,-1);
		else if(op==3) printf("%d\n",getrk(rt[qwq],x));
		else if(op==4) printf("%d\n",getkth(rt[qwq],x));
		else if(op==5) printf("%d\n",getkth(rt[qwq],getrk(rt[qwq],x)-1));
		else if(op==6) printf("%d\n",getkth(rt[qwq],getrk(rt[qwq],x+1)));
//		cout << a[rt[qwq]].sz << endl;
	}
	return 0;
}