替罪羊树MLE求调

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct hhh{
	int ls,rs,w,wn,s,sz,sd;
}dl[N];
int n,op,x,rt,cnt;
int id[N],sum;
double arf=0.7;
void pushup(int bh){
	int l=dl[bh].ls,r=dl[bh].rs;
	dl[bh].s=dl[l].s+dl[r].s+1;
	dl[bh].sz=dl[l].sz+dl[r].sz+dl[bh].wn;
	dl[bh].sd=dl[l].sd+dl[r].sd+(dl[bh].wn!=0); 
}
bool cheak(int p){
	if(!dl[p].wn) return 0;
	if(arf*dl[p].s<=(double)max(dl[dl[p].ls].s,dl[dl[p].rs].s)) return 1;
	if((double)dl[p].sd<=arf*dl[p].s) return 1;
	return 0;
}
void work(int p){
	if(!p) return;
	work(dl[p].ls);
	if(dl[p].wn) id[++sum]=p;
	work(dl[p].rs);
}
int build(int l,int r){
	if(l>=r) return 0;
	int mid=(l+r)>>1;
	dl[id[mid]].ls=build(l,mid);
	dl[id[mid]].rs=build(mid+1,r);
	pushup(id[mid]);
	return id[mid];
}
void rbuild(int &p){
	sum=0;
	work(p); 
	build(1,sum);
}
void add(int &p,int x){
	if(!p){
		p=++cnt;
		dl[p].w=x;
		dl[p].ls=dl[p].rs=0;
		dl[p].wn=dl[p].s=dl[p].sz=dl[p].sd=1;
		return;
	}
	if(dl[p].w==x) dl[p].wn++;
	else if(dl[p].w<x) add(dl[p].rs,x);
	else add(dl[p].ls,x);
	pushup(p);
	if(cheak(p)) rbuild(p);
}
void del(int &p,int x){
	if(!p) return;
	if(dl[p].w==x){dl[p].wn--;return;}
	if(dl[p].w<x) del(dl[p].rs,x);
	else del(dl[p].ls,x);
	pushup(p);
	if(cheak(p)) rbuild(p);
}
int upbon(int p,int x){
	if(!p) return 1;
	if(dl[p].w==x&&dl[p].wn) return dl[dl[p].ls].sz+dl[p].wn+1;
	if(dl[p].w>x) return upbon(dl[p].ls,x);
	return dl[dl[p].ls].sz+dl[p].wn+upbon(dl[p].rs,x);
}
int swapbon(int p,int x){
	if(!p) return 0;
	if(dl[p].w==x&&dl[p].wn) return dl[dl[p].ls].sz;
	if(dl[p].w>x) return swapbon(dl[p].ls,x);
	return dl[dl[p].ls].sz+dl[p].wn+swapbon(dl[p].rs,x);
}
int getk(int p,int x){
	if(!p) return 0;
	if(dl[dl[p].ls].sz<x&&dl[dl[p].ls].sz+dl[p].wn>=x) return dl[p].w;
	if(dl[dl[p].ls].sz+dl[p].wn<x) return getk(dl[p].rs,x-dl[dl[p].ls].sz-dl[p].wn);
	return getk(dl[p].ls,x); 
}
int pre(int x){
	return getk(rt,swapbon(rt,x));
}
int nxt(int x){
	return getk(rt,upbon(rt,x));
}
int main(){
	cin>>n;
	while(n--){
		cin>>op>>x;
		if(op==1) add(rt,x);
		if(op==2) del(rt,x);
		if(op==3) cout<<swapbon(rt,x)+1<<endl;
		if(op==4) cout<<getk(rt,x)<<endl;
		if(op==5) cout<<pre(x)<<endl;
		if(op==6) cout<<nxt(x)<<endl;
	}
	return 0;
}