rt

P5076【深基16.例7】普通二叉树（简化版）

此为代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define ll long long
#define re register
#define il inline
using namespace std;
const int maxans=2147483647;
const int minans=-2147483647;
int n;
int cntt=0;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct Node{
	int w,l,r,cnt,s;
}node[500010];
il void add(int x,int y){
	node[x].s++;
	if(node[x].w==y){
		node[x].cnt++;
		return;
	}
	else if(node[x].w>y){
		if(!node[x].l){
			cntt++;
			node[x].l=cntt;
			node[cntt].w=y;
			node[cntt].s=1;
			node[cntt].cnt=1;
		}
		else add(node[x].l,y);
	}
	else {
		if(!node[x].r){
			cntt++;
			node[x].r=cntt;
			node[cntt].w=y;
			node[cntt].s=1;
			node[cntt].cnt=1;
		}
		else {
			add(node[x].r,y);
		}
	}
}
il int pre(int x,int y,int ans){
	if(node[x].w>=y){
		if(!node[x].l){
			return ans;
		}
		else {
			return pre(node[x].l,y,ans);
		}
	}
	else {
		if(!node[x].r){
			return node[x].w<y ? node[x].w : ans;
		}
		if(node[x].cnt){
			ans=node[x].w;
		}
		return pre(node[x].r,y,ans);
	}
}
il int nex(int x,int y,int ans){
	if(node[x].w<=y){
		if(!node[x].r){
			return ans;
		}
		else {
			return nex(node[x].r,y,ans);
		}
	}
	else {
		if(!node[x].l){
			return node[x].w>y ? node[x].w : ans;
		}
		if(node[x].cnt){
			ans=node[x].w;
		}
		return nex(node[x].l,y,ans);
	}
}
il int findnum(int x,int rank){
	if(x==0)return maxans;
	if(node[node[x].l].s>=rank){
		return findnum(node[x].l,rank);
	}
	else if(node[node[x].l].s+node[x].cnt>=rank){
		return node[x].w;
	}
	else {
		return findnum(node[x].r,rank-node[node[x].l].s-node[x].cnt);
	}
}
il int findrank(int x,int num){
	if(x==0)return 0;
	if(num==node[x].w){
		return node[node[x].l].s+1;
	}
	else if(num<node[x].w){
		return findrank(node[x].l,num);
	}
	else {
		return findrank(node[x].r,num)+node[node[x].l].s+node[x].cnt;
	}
}
/*il void del(){
	
}*/
int main(){
	n=read();
	for(re int i=1;i<=n;i++){
		int op,num;
		op=read();
		num=read();
		if(op==1){
			printf("%d\n",findrank(1,num)+1);
		}
		else if(op==2){
			printf("%d\n",findnum(1,num));
		}
		else if(op==3){
			printf("%d\n",pre(1,num,minans));
		}
		else if(op==4){
			printf("%d\n",nex(1,num,maxans));
		}
		else if(op==5){
			if(cntt==0){
				cntt++;
				node[cntt].cnt=1;
				node[cntt].s=1;
				node[cntt].w=num;
			}
			else add(1,num);
		}
	}
	return 0;
} 

码风不好还请见谅