这题交上去9个点T，不是常数的问题，感觉Splay板子写的没毛病 /kk

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.1e+5+100;
const int inf = 0x7fffffff;
int n,m,rt,tot;
int f[maxn],ch[maxn][2],val[maxn],siz[maxn],cnt[maxn];

int read(){
	int v=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f = -f; c = getchar();}
	while(c>='0'&&c<='9'){v = (v<<3)+(v<<1) + c -'0'; c= getchar();}
	return v*f;
}

void pushup(int x){
	siz[x] = siz[ch[x][0]] + cnt[x] + siz[ch[x][1]];
}
int get(int x){
	return ch[f[x]][1] == x;
}
void connect(int s,int fa,int dir){
	f[s] = fa;
	ch[fa][dir] = s;
}
void rotate(int x){
	int fa=f[x],gfa = f[fa];
	int s1=get(x),s2=get(fa);
	int s = ch[x][s1^1];
	connect(s,fa,s1);
	connect(x,gfa,s2);
	connect(fa,x,s1^1);
	pushup(fa);
	pushup(x);
}
void Splay(int x,int gol){
	for(int fa;(fa=f[x])&&fa!=gol;rotate(x)){
		if(f[fa]!=gol)rotate(get(x)==get(fa)?fa:x);
	}
	if(!gol) rt = x;
}
void ins(int x){
	int cur = rt,fa=0;
	while(cur&&x!=val[cur]){
		fa = cur;
		cur = ch[cur][x>val[cur]];
	}
	if(cur){
		++cnt[cur];
	}else{
		cur = ++tot;
		val[cur] = x;
		f[cur] = fa;
		if(fa) ch[fa][x>val[fa]] = cur;
		siz[cur] = cnt[cur] = 1;
	}
	Splay(cur,0);
}
int kth(int k){
	int cur=rt;
	while(true){
		int s=ch[cur][0];
		//printf("gyx %d %d %d\n",k,val[rt],cnt[cur]);
		if(k<=siz[ch[cur][0]]){
			cur = s;
		}else if(k>siz[ch[cur][0]]+cnt[cur]){
			cur = ch[cur][1];
			k-=siz[ch[cur][0]] + cnt[cur];
		}else{
			Splay(cur,0);
			return cur;
		}
	}
}
int main(){
	n=read();
	//ins(inf);ins(-inf);
	for(register int i=1;i<=n;++i){
		int x=read();
		ins(x);
	}
	m=read();
	while(m--){ 
		string opt;
		int x;
		cin>>opt;
		//printf("myc %s\n",opt);
		if(opt[0]=='a'){
			x=read();
			ins(x);
			++n;
		}
		if(opt[0]=='m'){
			printf("%d\n",(n&1)?val [kth (n/2+1)]: val [kth (n/2)]);
		}
	}
	return 0;
}