萌新求助

# include <bits/stdc++.h>
# define rr register
const int N=100010;
int c[N],b[N];
int n,m,q;
int opt[N][2];
int tree[N*4];
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;		
}
inline int lc(int x){
	return x<<1;
}
inline int rc(int x){
	return x<<1|1;
}
void Insert(int k,int l,int r,int v){
	if(l==r){
		++tree[k];	
		return;
	}
	int mid=(l+r)>>1;
	if(v<=mid)
		Insert(lc(k),l,mid,v);
	else
		Insert(rc(k),mid+1,r,v);
	tree[k]=tree[lc(k)]+tree[rc(k)];	
	return;		
}
int GetRankFindVal(int k,int l,int r,int x){
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	if(x<=tree[lc(k)])
		return GetRankFindVal(lc(k),l,mid,x);
	return GetRankFindVal(rc(k),mid+1,r,x-tree[lc(k)]);
}
int main(void){
	n=read();
	for(rr int i=1;i<=n;++i){
		b[i]=c[i]=read();
	}
	m=n;
	q=read();
	char sign[10];
	for(rr int i=1;i<=q;++i){
		scanf("%s",sign);
		if(sign[0]=='a'){
			opt[i][0]=1;
			opt[i][1]=read();
			b[++m]=opt[i][1];
		}
		else
			opt[i][0]=2;
	}
	std::sort(b+1,b+1+m);
	m=std::unique(b+1,b+1+m)-(b+1);
	int sum=n;
	for(rr int i=1;i<=n;++i)
		Insert(1,1,m,std::lower_bound(b+1,b+1+m,c[i])-b);
	for(rr int i=1;i<=q;++i){
		if(opt[i][0]==1){
			Insert(1,1,m,std::lower_bound(b+1,b+1+m,opt[i][1])-b);
			++sum;
		}
		else printf("%d\n",b[GetRankFindVal(1,1,m,(sum+1)>>1)]);
	}
	return 0;
}