社区讨论

请求各位大佬调教 成功后必关注

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@m6rl74ix
此快照首次捕获于
2025/02/05 15:28
去年
此快照最后确认于
2025/11/04 09:58
4 个月前
查看原帖
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 rank(int x,int root){
	if(root){
		if(x<t[root].value)
			return rank(x,t[root].left);
		if(x<t[root].value)
			return rank(x,t[root].right)+t[t[root].left].size+t[root].num;
		return t[t[root].left].size+t[root].num;
	}
	return 1;
}
int kth(int x,int root){
	if(x<=t[t[root].left].left)
		return kth(x,t[root].left);
	if(x<=t[t[root].left].left+t[root].num)
		return t[root].value;
	return kth(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(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	int num=0;
	t[root=++cnt]=Node(0,0,1,2147483647);
	while(n--){
		cin>>opt>>x;
		num++;
		if(opt==1)cout<<rank(x,root)<<endl;
		else if(opt==2)cout<<kth(x,root)<<endl;
		else if(opt==3)cout<<kth(rank(x,root)-1,root)<<endl;
		else if(opt==4)cout<<kth(rank(x+1,root),root)<<endl;
		else num--,insert(x,root);
	}
	return 0;
}

回复

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

正在加载回复...