这份splay平衡树没过样例但是ac了本题

#include<bits/stdc++.h>
using namespace std;
int root,tot;
struct splay_tree{
	int ch[2],siz,cnt,fa,val;
}tree[200005];
void update(int x){
    tree[x].siz=tree[tree[x].ch[0]].siz+tree[tree[x].ch[1]].siz+tree[x].cnt;
    return ;
}
bool get(int x){
	return x==tree[tree[x].fa].ch[1];
}
void rotate(int x){
	int y=tree[x].fa;//指向自己的父亲 
	int z=tree[y].fa;//指向祖父 
	int chk=get(x);//自己是否是父亲的右儿子，选择操作类型 
	tree[y].ch[chk]=tree[x].ch[chk^1];//xor运算使得相同值为假，不同值为真 
	if(tree[x].ch[chk^1]){//如果你的左or右儿子为空 
		tree[tree[x].ch[chk^1]].fa=y;//父亲的左or右儿子的父亲指向自己的父亲 
	}
	tree[x].ch[chk^1]=y;//否则你的左or右儿子指向自己的父亲 
	tree[y].fa=x;//把x这条边指向你要rotate的对象 
	tree[x].fa=z;//把rotate对象的父亲指向祖父 
	if(z){
		tree[z].ch[y==tree[z].ch[1]]=x;//把祖父的左or右儿子判断是否为父亲的左or右儿子然后指向rotate对象 
	}
	update(y);//上传父亲size 
	update(x);//上传对象size 
	return ;
}
void splay(int x){
	for(int f=tree[x].fa;f=tree[x].fa,f;rotate(x))
		if(tree[f].fa)
			rotate(get(x)==get(f)?f:x);
	root=x;
}
void clear(int x){
	tree[x].ch[0]=tree[x].ch[1]=tree[x].fa=tree[x].val=tree[x].cnt=tree[x].siz=0;
	return ;
}
void insert(int k){
	if(!root){//如果不是根 
		tree[++tot].val=k;
		tree[tot].cnt++;
		root=tot;
		update(root);
		return;
	}
	int cur=root,f=0;
	while(1){//递归旋转插入 
		if(tree[cur].val==k){
			tree[cur].cnt++;
		    update(cur);
			update(f);
			splay(cur);
			break;
		}
		f=cur;
		cur=tree[f].ch[tree[f].val<k];
		if(!cur){
			tree[++tot].val=k;
			tree[tot].cnt++;
			tree[tot].fa=f;
			tree[f].ch[tree[f].val<k]=tot;
			update(tot);
			update(f);
			splay(tot);
			break;
		}
	}
}
int rnk(int x){
	int res=0,cur=root;
	while(1){
		if(x<tree[cur].val)
			cur=tree[cur].ch[0];
		else{
			res+=tree[tree[cur].ch[0]].siz;
			if(x==tree[cur].val){
				splay(cur);
				return res+1;
			}
			res+=tree[cur].cnt;
			cur=tree[cur].ch[1];
		}
	}
}
int kth(int x){
	int cur=root;
	while(1){
		if(tree[cur].ch[0]&&x<=tree[tree[cur].ch[0]].siz){
		    cur=tree[cur].ch[0];
	    }
	    else{
		    x-=tree[tree[cur].ch[0]].siz+tree[cur].cnt;
		    if(x<=0){
			    splay(cur);
			    return tree[cur].val;
		    }
		    cur=tree[cur].ch[1];
	    }
	}
}
int pre(){
	int cur=tree[root].ch[0];
	if(!cur){
		return cur;
	}
	while(tree[cur].ch[1]){
		cur=tree[cur].ch[1];
	}
	splay(cur);
	return cur;
}
int next(){
	int cur=tree[root].ch[1];
	if(!cur){
		return cur;
	}
	while(tree[cur].ch[0]){
		cur=tree[cur].ch[0];
	}
	splay(cur);
	return cur;
}
void del(int x){
	rnk(x);
	if(tree[root].cnt>1){
		tree[root].cnt--;
		update(root);
		return ;
	}
	if(!tree[root].ch[0]&&!tree[root].ch[1]){
		clear(root);
		root=0;
		return ;
	}
	if(!tree[root].ch[0]){
		int cur=root;
		root=tree[root].ch[1];
		tree[root].fa=0;
		clear(cur);
		return ;
	}
	if(!tree[root].ch[1]){
		int cur=root;
		root=tree[root].ch[0];
		tree[root].fa=0;
		clear(cur);
		return ;
	}
	int cur=root;
	int k=pre();
	tree[tree[cur].ch[1]].fa=root;
	tree[root].ch[1]=tree[cur].ch[1];
	clear(cur);
	update(root);
	return ;
}
int n,m,num;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		num++;
		scanf("%d",&x);
		insert(x);
	}
	scanf("%d",&m);
	char a[3];
	for(int i=1;i<=m;i++){
		int x;
		scanf("%s%d",a,&x);
		if(a[0]=='a'){
			num++;
			insert(x);
		}
		else{
			printf("%d\n",kth((num+1)>>1));
		}
	}
	return 0;
}