rt，暴力 BST

样例过了提交 0 分

可以帮忙看看吗 qwq

#include<iostream>
using namespace std;
const int N=100010;
int cnt[N];
int siz[N];
int idx;
const int INF=0x7fffffff;

struct node{
	int lc,rc,fa,val;
	bool is_lc;
}bst[N];

void inorder(int u){
	if(u==0) return ;
	inorder(bst[u].lc);
	for(int i=1;i<=cnt[u];++i) cout<<bst[u].val;
	inorder(bst[u].rc);
}

//query：在以u为根节点的子树中找权值为v的节点编号
int find(int u,int v){
	if(u==0 || v==bst[u].val) return u;
	if(v<bst[u].val) return find(bst[u].lc,v);
	else return find(bst[u].rc,v);
} 

//查询max/min
int find_min(int u){
	if(bst[u].lc==0) return u;
	return find_min(bst[u].lc);
} 

int find_max(int u){
	if(bst[u].rc==0) return u;
	return find_max(bst[u].rc);
}

//插入：在u节点挂上一个权值为v新节点
int add(int u,int v,bool lr){
	bst[++idx].val=v;
	bst[idx].fa=u;
	bst[idx].is_lc=lr;
//	bst[idx].lc=bst[idx].rc=0;
	cnt[idx]=siz[idx]=1;
	return idx;
}

void insert(int u,int v){
	if(u==1 && siz[1]==0){//树是空的 
		add(0,v,1);
		return;
	}
	siz[u]++;
	if(bst[u].val==v){//重复值，不增加节点 
		cnt[u]++;
		return;
	}
	if(v<bst[u].val){
		//加到左子树
		if(bst[u].lc==0) bst[u].lc=add(u,v,1);
		else insert(bst[u].lc,v); 
	}
	if(v>bst[u].val){
		//加到右子树
		if(bst[u].rc==0) bst[u].rc=add(u,v,0);
		else insert(bst[u].rc,v); 
	}
} 

//在u为根节点的子树里删除权值为v的节点
void del(int u,int v){
	if(find(u,v)==0) return;
	if(siz[u]==0) return;
	siz[u]--;
	if(bst[u].val==v){
		if(cnt[u]>1){
		 	cnt[u]--;//若有多个，随便删一个
		 	return;
		}
		int p=bst[u].fa;
		bool p_lc=bst[u].is_lc;
		if(bst[u].lc==0 && bst[u].rc==0){
			//u为叶子节点
			if(p_lc) bst[p].lc=0;
			else bst[p].rc=0;
		}
		else if(bst[u].lc && bst[u].rc==0){
			//左链
			if(p_lc) bst[p].lc=bst[u].lc;
			else bst[p].rc=bst[u].lc; 
		}
		else if(bst[u].lc==0 && bst[u].rc){
			//右链
			if(p_lc) bst[p].lc=bst[u].rc;
			else bst[p].rc=bst[u].rc; 
		}
		else if(bst[u].lc && bst[u].rc){
			//二叉树  选择右子树最小节点进行替换
			int r_min=find_min(bst[u].rc);
			bst[u].val=bst[r_min].val;
			del(bst[u].rc,bst[r_min].val);//删除替罪羊 
		}
		return;
	} 
	if(v<bst[u].val) del(bst[u].lc,v);
	if(v>bst[u].val) del(bst[u].rc,v);
}
 
//求rank
int query_rank(int u,int v){
	if(find(u,v)==0) return -1;//不存在
	if(v==bst[u].val) return siz[bst[u].lc]+1;
	if(v<bst[u].val) return query_rank(bst[u].lc,v);
	if(v>bst[u].val) return query_rank(bst[u].rc,v)+siz[bst[u].lc]+cnt[u];
} 

//返回第k大值
int query_kth(int u,int k){
	if(k<1 || k>siz[u]) return -1;
	if(k<=siz[bst[u].lc]) return query_kth(bst[u].lc,k);
	if(k>siz[bst[u].lc]+cnt[u]) return query_kth(bst[u].rc,k-siz[bst[u].lc]-cnt[u]);
	//就在u上
	return bst[u].val;	
} 
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		int opt,x; cin>>opt>>x;
		if(opt==1) cout<<query_rank(1,x)<<endl;
		else if(opt==2) cout<<query_kth(1,x)<<endl;
		else if(opt==3){
			int rk=query_rank(1,x);
			if(rk==1) cout<<-2147483647<<endl; 
			else cout<<query_kth(1,rk-1)<<endl;
		}
		else if(opt==4){
			int rk=query_rank(1,x);
			if(rk==idx) cout<<2147483647<<endl;
			else cout<<query_kth(1,rk+1)<<endl;
		}
		else insert(1,x);
	}
	return 0;
}