删除写的有问题，没调出来，救救孩子吧
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int tot,root;
bool flag;
int n,m;
struct node{
int ch[2],fa;
int h,bal,size;//树高和平衡因子
int val;
}bst[N];
int newnode(int val,int fa){
bst[++tot].val=val;bst[tot].fa=fa;
bst[tot].h=1;//初始化树高
bst[tot].bal=0; bst[tot].size=1;
return tot;
}
/*
10 100
7 4 5 3 1 9 8 2 6 10
*/
int search_bst(int p,int val){
if(p==0) return 0;
if(bst[p].val==val){
//cout<<"high: "<<bst[p].h<<endl;
//cout<<"size: "<<bst[p].size<<endl;
//cout<<"balance: "<<bst[p].bal<<endl;
return p;
}
else if(val<bst[p].val) return search_bst(bst[p].ch[0],val);
else return search_bst(bst[p].ch[1],val);
}
int Rank(int p,int x,int rk){
if(p==0) return 114514;
if(rk==x) return bst[p].val;
else if(rk>x) return Rank(bst[p].ch[0],x,rk-bst[bst[bst[p].ch[0]].ch[1]].size-1);//递归左子树
else return Rank(bst[p].ch[1],x,rk+bst[bst[bst[p].ch[1]].ch[0]].size+1);//递归右子树
}
int x_rank(int p,int x,int rk){
//cout<<"rk: "<<rk<<endl;
if(bst[p].val==x){
//cout<<"have val"<<endl;
return rk;
}
else if(x<bst[p].val){//递归左子树'
if(bst[p].ch[0]==0) return rk;
else return x_rank(bst[p].ch[0],x,rk-bst[bst[bst[p].ch[0]].ch[1]].size-1);
}
else{
if(bst[p].ch[1]==0) return rk+1;
else return x_rank(bst[p].ch[1],x,rk+bst[bst[bst[p].ch[1]].ch[0]].size+1);
}
}
int x_front(int p,int x,int fr){
if(p==0) return fr;
if(x<=bst[p].val) return x_front(bst[p].ch[0],x,fr);
else return x_front(bst[p].ch[1],x,max(fr,bst[p].val));//比x小
}
int x_back(int p,int x,int bk){
if(p==0) return bk;
if(x<bst[p].val) return x_back(bst[p].ch[0],x,min(bk,bst[p].val));//比x
else return x_back(bst[p].ch[1],x,bk) ;
}
int getfa(int p){
return bst[bst[p].fa].ch[0]==p?0:1;
}
void update(int p){
bst[p].h=max(bst[bst[p].ch[0]].h,bst[bst[p].ch[1]].h)+1;//更新树高
bst[p].bal=bst[bst[p].ch[0]].h-bst[bst[p].ch[1]].h;//更新平衡因子
bst[p].size=bst[bst[p].ch[0]].size+bst[bst[p].ch[1]].size+1;//更新子树大小
}
void rotate(int x){//以x为支点旋转他的父亲节点
int s,y,z;
y=bst[x].fa;s=getfa(x);z=bst[x].ch[s^1];//要旋转的节点和可能发生冲突的节点
if(y==root) {
//cout<<"rotate root "<<endl;
root=x;
}
else {bst[bst[y].fa].ch[getfa(y)]=x;bst[x].fa=bst[y].fa;}
bst[y].ch[s]=z;bst[x].ch[s^1]=y;
bst[y].fa=x;bst[z].fa=y;
update(y);update(x);
}
void check(int p){//发生失衡
if(abs(bst[p].bal)>1){
//cout<<"No Balance "<<bst[p].val<<endl;
if(bst[p].bal==2&&bst[bst[p].ch[0]].bal==1){//LL
rotate(bst[p].ch[0]);
}
else if(bst[p].bal==-2&&bst[bst[p].ch[1]].bal==-1){//RR
rotate(bst[p].ch[1]);
}
else if(bst[p].bal==2&&bst[bst[p].ch[0]].bal==-1){//LR
rotate(bst[bst[p].ch[0]].ch[1]);
rotate(bst[p].ch[0]);
}
else{//RL
rotate(bst[bst[p].ch[1]].ch[0]);
rotate(bst[p].ch[1]);
}
}
}
void insert_bst(int &p,int fa,int val){
if(p==0){
p=newnode(val,fa);//p是引用
if(root==0) root=p;
return;
}
if(bst[p].val==val) return;
else if(val<bst[p].val) insert_bst(bst[p].ch[0],p,val);
else insert_bst(bst[p].ch[1],p,val);
update(p);
check(p);
}
void delete_bst(int &p,int val){
//return ;
if(p==0) return;
if(bst[p].val==val){
if(p==root) flag=1;
if(bst[p].ch[0]==0&&bst[p].ch[1]==0) {p=0;}
else if(bst[p].ch[0]==0) p=bst[p].ch[1];
else if(bst[p].ch[1]==0) p=bst[p].ch[0];
else{//有左右子树
//return ;
int x=bst[p].ch[0];
while(bst[x].ch[1]){//找到左子树最大
x=bst[x].ch[1];
}
bst[p].val=bst[x].val;
delete_bst(bst[p].ch[0],bst[x].val);
}
if(flag) {root=p;flag=0;}
}
else if(val<bst[p].val) delete_bst(bst[p].ch[0],val);
else delete_bst(bst[p].ch[1],val);
update(p);
check(p);
}
int main(){
cin>>m;
while(m--){
int op,x;
cin>>op;
if(op==1){//插入
cin>>x;
insert_bst(root,root,x);
}
else if(op==2){//删除
cin>>x;
//if(x==577793) continue;
delete_bst(root,x);
}
else if(op==3){//x的排名
cin>>x;
cout<<x_rank(root,x,bst[bst[root].ch[0]].size+1)<<endl;
}
else if(op==4){//排名为k
cin>>x;
cout<<Rank(root,x,bst[bst[root].ch[0]].size+1)<<endl;
}
else if(op==5){
cin>>x;
cout<<x_front(root,x,-INT_MAX)<<endl;
}
else{
cin>>x;
cout<<x_back(root,x,INT_MAX)<<endl;
}
}
//system("pause");
return 0;
}