21pts求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 9;

struct node{
	int l_son,r_son;
	int val,pri;
	int num,size;
}tree[MAXN];
int cnt,root;


int New(int val){
	tree[++cnt].val = val;
	tree[cnt].pri = rand();
	tree[cnt].num = 1;
	tree[cnt].size = 1;
	tree[cnt].l_son = 0;
	tree[cnt].r_son = 0;
	return cnt;
}

void Update(int p){
	tree[p].size = tree[tree[p].l_son].size + tree[tree[p].r_son].size + tree[p].num;
}

void zig(int &p){ //右旋
	int q = tree[p].l_son;
	tree[p].l_son = tree[q].r_son;
	tree[q].r_son = p;
	tree[q].size = tree[p].size;
	Update(p);
	p = q;
}

void zag(int &p){ //左旋
	int q = tree[p].r_son;
	tree[p].r_son = tree[q].l_son;
	tree[q].l_son = p;
	tree[q].size = tree[p].size;
	Update(p);
	p = q;
}

void Insert(int &p,int val){
	if(!p){
		p = New(val);
		return;
	}
	tree[p].size++;
	if(val == tree[p].val){
		tree[p].num++;
		return;
	}
	if(val < tree[p].val){
		Insert(tree[p].l_son,val);
		if(tree[p].pri < tree[tree[p].l_son].pri){
			zig(p);
		}
	}else{
		Insert(tree[p].r_son,val);
		if(tree[p].pri < tree[tree[p].r_son].pri){
			zag(p);
		}
	}
}

void Delete(int &p,int val){ //在 p 的子树中删除 val 
	if(!p){
		return;
	}
	tree[p].size--;
	if(tree[p].val == val){
		if(tree[p].num > 1){
			tree[p].num--;
			return;
		}
		if(!tree[p].l_son || !tree[p].r_son){
			p = tree[p].l_son + tree[p].r_son;
		}else if(tree[tree[p].l_son].pri > tree[tree[p].r_son].pri){
			zig(p);
			Delete(tree[p].r_son,val);
		}else{
			zag(p);
			Delete(tree[p].l_son,val);
		}
		return;
	}
	if(val < tree[p].val){
		Delete(tree[p].l_son,val);
	}else{
		Delete(tree[p].r_son,val);
	}
}

int GetPre(int val){
	int p = root;
	int res = 0;
	while(p){
		if(tree[p].val < val){
			res = tree[p].val;
			p = tree[p].r_son;			
		}else{
			p = tree[p].l_son;
		}
	}
	return res;
}

int GetNext(int val){
	int p = root;
	int res = 0;
	while(p){
		if(tree[p].val > val){
			res = tree[p].val;
			p = tree[p].l_son;			
		}else{
			p = tree[p].r_son;
		}
	}
	return res;
}

int GetRankByVal(int p,int val){
	if(!p){
		return 0;
	}
	if(tree[p].val == val){
		return tree[tree[p].l_son].size + 1;
	}
	if(tree[p].val > val){
		return GetRankByVal(tree[p].l_son,val);
	}else{
		return GetRankByVal(tree[p].r_son,val);
	}
}

int GetValByRank(int p,int rank){
	if(!p){
		return 0;
	}
	if(tree[tree[p].l_son].size >= rank){
		return GetValByRank(tree[p].l_son,rank);	
	}
	if(tree[tree[p].l_son].size + tree[p].num >= rank){
		return tree[p].val;
	}
	return GetValByRank(tree[p].r_son,rank - tree[tree[p].l_son].size - tree[p].num);
}

int n; 
int main(){
	cin >> n;
	root = 0;
	while(n--){
		int opt;
		cin >> opt;
		switch (opt){
			case 1:{
				int x;
				cin >> x;
				Insert(root,x);
				break;
			}
			case 2:{
				int x;
				cin >> x;
				Delete(root,x);
				break;
			}
			case 3:{
				int x;
				cin >> x;
				cout << GetRankByVal(root,x) << endl;
				break;
			}
			case 4:{
				int x;
				cin >> x;
				cout << GetValByRank(root,x) << endl;
				break;
			}
			case 5:{
				int x;
				cin >> x;
				cout << GetPre(x) << endl;
				break;
			}
			case 6:{
				int x;
				cin >> x;
				cout << GetNext(x) << endl;
				break;
			}
		}
	}
	return 0;
}