P5076 普通二叉树（简化版）

题目原文及输入/输出格式

题目描述

您需要写一种数据结构，来维护一些数（ 都是$10^9$以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数$q$不超过$10^4$：

1. 查询$x$数的排名（排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名）。

2. 查询排名为$x$的数。

3. 求$x$的前驱（前驱定义为小于$x$，且最大的数）。若未找到则输出-2147483647。

4. 求$x$的后继（后继定义为大于$x$，且最小的数）。若未找到则输出 2147483647。

5. 插入一个数$x$。

AC解法

模板题就不多说直接上代码。关于BST可以看我另一篇专门的文章。

struct tree{
	int left, right, val, size, cnt;
}T[10010];

int sum, n;

void add(int x, int v){
	T[x].size++;
	
	if(T[x].val==v){
		T[x].cnt++;
		return;
	}
	if(v<T[x].val){
		if(T[x].left!=0)
			add(T[x].left, v);
		else{
			T[x].left=++sum;
			T[sum].cnt=1;
			T[sum].size=1;
			T[sum].val=v;
		}
	}else{
		if(T[x].right!=0)
			add(T[x].right, v);
		else{
			T[x].right=++sum;
			T[sum].cnt=1;
			T[sum].size=1;
			T[sum].val=v;
		}
	}
} 

int querypre(int x, int val, int ans){
	if(T[x].val>=val){
		if(T[x].left==0) 
			return ans;
		else 
			querypre(T[x].left, val, ans);
	}else{
		if(T[x].right==0) 
			return T[x].val;
			
		if(T[x].cnt==0)
			return querypre(T[x].right, val, ans);
		else
			return querypre(T[x].right, val, T[x].val);
	}
}

int querynext(int x, int val, int ans){
	if(T[x].val<=val){
		if(T[x].right==0)
			return ans;
		else
			querynext(T[x].right, val, ans);
	}else{
		if(T[x].left==0)
			return T[x].val;
		
		if(T[x].cnt==0)
			return querynext(T[x].left, val, ans);
		else 
			return querynext(T[x].left, val, T[x].val);
	}
}

int queryrankfromval(int x, int val){
	if(x==0) return 0;
	
	if(T[x].val==val) return T[T[x].left].size+1;
	else if(T[x].val>val) return queryrankfromval(T[x].left, val);
	else return queryrankfromval(T[x].right, val)+T[x].cnt+T[T[x].left].size;
}

int queryvalfromrank(int x, int rank){
	if(T[T[x].left].size>=rank)
		return queryvalfromrank(T[x].left, rank);
	else if(T[T[x].left].size+T[x].cnt>=rank)
		return T[x].val;
	else 
		return queryvalfromrank(T[x].right, rank-T[T[x].left].size-T[x].cnt);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int a, b;
		cin>>a>>b;
		switch(a){
			case 1:{
				cout<<queryrankfromval(1, b)+1<<endl;
				break;
			}
			case 2:{
				cout<<queryvalfromrank(1, b)<<endl;
				break;
			}
			case 3:{
				cout<<querypre(1, b, -2147483647)<<endl;
				break;
			}
			case 4:{
				cout<<querynext(1, b, 2147483647)<<endl;
				break;
			}
			case 5:{
				if(i==1){
					T[i].val=b;
					T[i].cnt++;
					T[i].size++;
					sum++; 
				}else add(1, b);
				break;
			}
		}
	}
	return 0;
}