RT

用普通平衡树模板那粘过来的代码改了改也试了，五个点全T。

平衡树不应该比普通二叉搜索树快吗？

求助各位大佬。

代码如下（不用担心正确性，只是可能从那里粘过来的不符合题意？但是我检查过了，应该没有啊）：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define gen e[0].ch[1]
#define INF 2147483647
int q,n,po;
struct node{
	int ch[2],sum,rep,fa,v;
}e[MAXN];
inline int read(){
	int w=0,f=1;
	char c=getchar();
	while (c>'9'||c<'0'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		w=(w<<1)+(w<<3)+(c^48);
		c=getchar();
	}
	return w*f;
}
void addpo(int x,int fa){
	e[++n].fa=fa,e[n].rep=e[n].sum=1,e[n].v=x;
}
bool rship(int x){ return e[e[x].fa].ch[1]==x; }
void con(int son,int fa,int lr){
	e[son].fa=fa,e[fa].ch[lr]=son;
}
void ch(int x){ e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].rep; }
void turn(int x){
	int y=e[x].fa,ygen=e[y].fa,xship=rship(x),yship=rship(y),B=e[x].ch[xship^1];
	con(B,y,xship),con(y,x,xship^1),con(x,ygen,yship);
	ch(y),ch(x);
}
void splay(int at,int to){
	to=e[to].fa;
	while (e[at].fa!=to){
		int up=e[at].fa;
		if (e[up].fa==to) turn(at);
		else if (rship(up)==rship(at)) turn(up),turn(at);
		else turn(at),turn(at);
	} 
}
void add(int x){
	++po;
	if (po==1){
		gen=n+1;
		addpo(x,0);
	}else{
		int now=gen;
		while (1){
			e[now].sum++;
			if (e[now].v==x){
				e[now].rep++;
				splay(now,gen);
				return;
			}
			bool next=e[now].v<x;
			if (!e[now].ch[next]){
				addpo(x,now);
				e[now].ch[next]=n;
				splay(n,gen);
				return;
			}
			now=e[now].ch[next];
		}
	}
}
int find(int x){
	int now=gen;
	while (1){
		if (e[now].v==x){
			splay(now,gen);
			return now;
		}
		bool next=e[now].v<x;
		if (!e[now].ch[next]) return 0;
		now=e[now].ch[next];
	}
}
void kill(int x){
	e[x].fa=e[x].ch[0]=e[x].ch[1]=e[x].rep=e[x].sum=e[x].v=0;
	if (x==n) --n;
}
void pop(int x){
	int deal=find(x);
	if (!deal) return;
	--po;
	if (e[deal].rep>1){
		--e[deal].rep,--e[deal].sum;
		return;
	}
	if (!e[deal].ch[0]){
		gen=e[deal].ch[1];
		e[gen].fa=0;
	}else{
		int l=e[deal].ch[0],r=e[deal].ch[1];
		while (e[l].ch[1]) l=e[l].ch[1];
		splay(l,e[deal].ch[0]);
		con(r,l,1);con(l,0,1);
		ch(l);
	} 
	kill(deal);
}
int arank(int x){
	int now=gen,ans=0;
	while (1){
		if (e[now].v==x){
			ans+=1+e[e[now].ch[0]].sum;
			splay(now,gen);
			return ans;
		}
		if (e[now].v>x) now=e[now].ch[0];
		else{
			ans+=e[e[now].ch[0]].sum+e[now].rep;
			now=e[now].ch[1];
		}
	}
}
int rerank(int x){
	int now=gen;
	while (1){
		int cha=e[e[now].ch[0]].sum+e[now].rep;
		if (x>e[e[now].ch[0]].sum&&x<=cha){
			splay(now,gen);
			return e[now].v;
		}
		if (x<=e[e[now].ch[0]].sum) now=e[now].ch[0];
		else x-=cha,now=e[now].ch[1];
	}
}
int low(int x){
	int now=gen,ans=-INF;
	while (now){
		if (e[now].v<x&&e[now].v>ans) ans=e[now].v,splay(now,gen);
		if (e[now].v>=x) now=e[now].ch[0];
		else now=e[now].ch[1];
	}
	return ans;
}
int upp(int x){
	int now=gen,ans=INF;
	while (now){
		if (e[now].v>x&&e[now].v<ans) ans=e[now].v,splay(now,gen);
		if (e[now].v<=x) now=e[now].ch[1];
		else now=e[now].ch[0];
	}
	return ans;
}
int main(){
	q=read();
	while (q--){
		int op=read(),x=read();
		if (op==1) printf("%d\n",arank(x));
		else if (op==2) printf("%d\n",rerank(x));
		else if (op==3) printf("%d\n",low(x));
		else if (op==4) printf("%d\n",upp(x));
		else add(x);
	} 
    return 0;
}