社区讨论
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 条回复,欢迎继续交流。
正在加载回复...