替罪羊树wa&MLE 51pts

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long n,cnt,rt;
long long ls[N],rs[N],tot,siz[N],val[N],v[N],tmp[N],sum[N];
void pushup(int x){
	siz[x]=siz[ls[x]]+siz[rs[x]]+sum[x];
}
int build(int l,int r){
	if(l>r){
		return 0;
	}
	int mid=l+r>>1;
	int x=tmp[mid];
	val[x]=v[mid];
	sum[x]++;
	ls[x]=build(l,mid-1);
	rs[x]=build(mid+1,r);
	pushup(x);
	return x;
}
void flatten(int x){
	if(!x){
		return;
	}
	flatten(ls[x]);
	while(sum[x]){
		tmp[++cnt]=x;
		v[cnt]=val[x];
		sum[x]--;
	}
	flatten(rs[x]);
	ls[x]=rs[x]=0;
	siz[x]=0;
}
int rebuild(long long x){
	cnt=0;
	flatten(x);
	return build(1,cnt);
}
void insert(long long &root,int x){ 
	if(!root){
		root=++tot;
		sum[tot]++;
		val[tot]=x;
	}
	else if(x==val[root]){
		sum[root]++;
	}
	else if(x<val[root]){
		insert(ls[root],x);
	}
	else if(x>val[root]){
		insert(rs[root],x);
	}
	pushup(root);
	if((double)max(siz[ls[root]],siz[rs[root]])>=(double)siz[root]*0.7){
		root=rebuild(root);
	}
}
void dfs(int k,int x){
	if(rs[k]){
		dfs(rs[k],x);
	}
	else{
		rs[k]=x;
	}
}
void del(long long &root,int x){
	if(x==val[root]){
		sum[root]--;
		if(!ls[root]&&!rs[root]){
			root=0;
		}
		else if(!rs[root]){
			int tt=ls[root];
			ls[root]=0;
			root=tt;
		} 
		else if(!ls[root]){
			int tt=rs[root];
			rs[root]=0;
			root=tt;
		}
		else{
			dfs(ls[root],rs[root]);
			rs[root]=0;
			root=ls[root];
		}
	}
	else if(x<val[root]){
		del(ls[root],x);
	}
	else if(x>val[root]){
		del(rs[root],x);
	}
	pushup(root);
	if((double)max(siz[ls[root]],siz[rs[root]])>=(double)siz[root]*0.7){
		root=rebuild(root);
	}
}
long long check(int root,int x){
	if(!root){
		return 0;
	}
	else if(x==val[root]){
		return siz[ls[root]];
	}
	else if(x<val[root]){
		return check(ls[root],x);
	}
	else if(x>val[root]){
		return siz[ls[root]]+sum[root]+check(rs[root],x);
	}
}
long long rk(int root,int x){
	if(x>siz[ls[root]]&&x<=siz[ls[root]]+sum[root]){
		return val[root];
	}
	else if(x<=siz[ls[root]]&&ls[root]){
		return rk(ls[root],x);
	}
	else if(x>siz[ls[root]]+sum[root]&&rs[root]){
		return rk(rs[root],x-siz[ls[root]]-sum[root]);
	}
	return 0;
}
long long fir(int root,int x,long long k){
	if(x>=val[root]&&rs[root]==0){
		return val[root];
	}
	else if(x<=val[root]&&ls[root]){
		return fir(ls[root],x,k);
	}
	else if(x>val[root]&&rs[root]){
		return fir(rs[root],x,max(val[root],k));
	}
	return k;
}
long long lst(int root,int x,long long k){
	if(x<=val[root]&&ls[root]==0){
		return val[root];
	}
	else if(x<val[root]&&ls[root]){
		long long tt=min(val[root],k);
		return lst(ls[root],x,tt);
	}
	else if(x>=val[root]&&rs[root]){
		return lst(rs[root],x,k);
	}
	return k;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int opt,x;
		cin>>opt>>x;
		if(opt==1) insert(rt,x);
		else if(opt==2) del(rt,x);
		else if(opt==3) {
			cout<<check(rt,x)+1<<"\n";
		}
		else if(opt==4){
			cout<<rk(rt,x)<<"\n";
		}
		else if(opt==5) {
			cout<<fir(rt,x,0)<<"\n";
		}
		else if(opt==6) {
			cout<<lst(rt,x,1e18)<<"\n";
		}
	}
	return 0;
}