走过路过看一看 不要错过

是加进去/删除之后从根开始判断要不要重建的，然后重构了就跑路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,rot,gs;
double alpha=0.7;
double bmax(double x,double y){ return (x>y)?x:y; }
vector<int>vec;
struct scapegoat_tree{
	int val[N<<1],sz[N<<1],cnt[N<<1],tl[N<<1],tr[N<<1];
	void newnode(int &rt,int x,int cntx){
		rt=++gs; val[rt]=x; cnt[rt]=sz[rt]=cntx;
		tl[rt]=tr[rt]=0;
		return;
	}
	void ins(int &rt,int x) {
		//cout<<rt<<" "<<x<<endl;
		if(!rt){ newnode(rt,x,1); return; }
		if(x<val[rt]) ins(tl[rt],x);
		else if(x>val[rt]) ins(tr[rt],x);
		else cnt[rt]++;
		sz[rt]=sz[tl[rt]]+sz[tr[rt]]+cnt[rt];
		return;
	}
	void del(int rt,int x) {
		if(x<val[rt]) del(tl[rt],x);
		else if(x>val[rt]) del(tr[rt],x);
		else cnt[rt]--;
		sz[rt]=sz[tl[rt]]+sz[tr[rt]]+cnt[rt];
	}
	void dfs(int rt){
		if(tl[rt]) dfs(tl[rt]);
		vec.push_back(rt);
		if(tr[rt]) dfs(tr[rt]);
		tl[rt]=tr[rt]=0;
	}
	void build(int &rt,int l,int r){
		if(l>r) return;
		int mid=(l+r)>>1; rt=vec[mid];
		build(tl[rt],l,mid-1);
		build(tr[rt],mid+1,r);
		sz[rt]=sz[tl[rt]]+sz[tr[rt]]+cnt[rt];
		return;
	}
	void rebuild(int &rt) {
		//前序遍历，拍扁重建。
		vec.clear(); dfs(rt);
		build(rt,0,(int)vec.size()-1);
	}
	bool isbad(int rt) {
		return (alpha*sz[rt]<bmax(sz[tl[rt]],sz[tr[rt]]));
	}
	void blc(int &rt,int x) {
		if(!rt) return;
		if(isbad(rt)) rebuild(rt);
		else {
			if(x<val[rt]) blc(tl[rt],x);
			else if(x>val[rt]) blc(tr[rt],x);
		}
		return;
	}
	int rk(int rt,int x){
		int ret=1;
		while(1){
			if(!rt) return ret;
			if(x<val[rt]) rt=tl[rt];
			else {
				if(x==val[rt]) return ret;
				else {
					ret+=sz[tl[rt]]+cnt[rt]; rt=tr[rt];
				}
			}
		}
	}
	int kth(int rt,int x){//x:有x-1个数比num小
		if(!rt) return 0;
		if(x<=sz[tl[rt]]) return kth(tl[rt],x);
		else {
			if(x==sz[tl[rt]]+cnt[rt]) return rt;
			return kth(tr[rt],x-sz[tl[rt]]-cnt[rt]);
		}
	}
	int pre(int x){
		//有rk(rot,x)-1个数比x小，因此他的后继有rk(rot,x)-2个数<=他。
		//当x在树里，rk(rot,x)-1不包括它本身，它的前继显然排名在rk(rot,x)及之前
		//当x不在树里，rk(rot,x)-1不会包括它自己。它的前继显然排名在rk(rot,x)及之前
		return kth(rot,rk(rot,x)-1);
	}
	int nxt(int x){
		//有rk(rot,x+1)-1个数比x+1小，因此他的后继有rk(rot,x)-1个数<=他。
		//当x在树里，rk(rot,x+1)-1就包括了它自己。显然它的后继>=那么多数
		//当x不在树里，rk(rot,x+1)-1不会包括它自己。显然它的后继>=那么多数
		return kth(rot,rk(rot,x+1));
	}
}tr;
int main(){
	//freopen("example.in","r",stdin);
	scanf("%d",&n);
	for(int i=1,opt,x;i<=n;i++){
		scanf("%d%d",&opt,&x);
		if(opt==1) tr.ins(rot,x),tr.blc(rot,x);
		if(opt==2) tr.del(rot,x),tr.blc(rot,x);
		if(opt==3) printf("%d\n",tr.rk(rot,x));
		if(opt==4) printf("%d\n",tr.val[tr.kth(rot,x)]);
		if(opt==5) printf("%d\n",tr.val[tr.pre(x)]);
		if(opt==6) printf("%d\n",tr.val[tr.nxt(x)]);
	}
	return 0;
}