社区讨论

MLE求助

P5076【深基16.例7】普通二叉树(简化版)参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo87gex8
此快照首次捕获于
2023/10/27 14:01
2 年前
此快照最后确认于
2023/10/27 14:01
2 年前
查看原帖
CPP
#include<iostream>
#define MAXN 100010
using namespace std;
int n,root,cnt,opt,x;
struct Node{
	int left,right,size,value,num;
	Node(int l,int r,int s,int v){
		left=l;
		right=r;
		size=s;
		value=v;
		num=1;
	}
	Node(){}
} t[MAXN];
inline void update(int root){
	t[root].size=t[t[root].left].size+t[t[root].right].size+t[root].num;
}
int paiming(int x,int root){
	if(root){
		if(x<t[root].value){
			return paiming(x,t[root].left);
		}
		if(x>t[root].value){
			return paiming(x,t[root].right) + t[t[root].left].size + t[root].num;
		}
		return t[t[root].left].size+1;
	}
	return 1;
}
int wh(int x,int root){
	if(x<=t[t[root].left].size){
		return wh(x,t[root].left);
	}
	if(x<=t[t[root].left].size+t[root].num){
		return t[root].value;
	}
	return wh(x-t[t[root].left].size -t[root].num,t[root].right);
}
void insert(int x,int root){
	if(x<t[root].value){
		if(!t[root].left){
			t[t[root].left = ++cnt]=Node(0,0,1,x);
		}
		else{
			insert(x,t[root].left);	
		}
	}
	else if(x>t[root].value){
		if(!t[root].right){
			t[t[root].right=++cnt]=Node(0,0,1,x);
		}
		else{
			insert(x,t[root].right);
		} 
	}
	else{
		t[root].num++;
		update(root);
	}
}
int main(){
	cin>>n;
	t[root=++cnt]=Node(0,0,1,2147483647);
	while(n--){
		cin>>opt>>x;
		if(opt==1){
			cout<<paiming(x,root)<<endl;
		}
	 	else if(opt==2){
	 		cout<<wh(x,root)<<endl;
		}
		else if(opt==3){
			cout<<wh(paiming(x,root)-1,root)<<endl;
		}
		else if(opt==4){
			cout<<wh(paiming(x,root)+1,root)<<endl;
		}
		else{
			insert(x,root);
		}
	}	
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...