指针二叉搜索树0pts求条
查看原帖
指针二叉搜索树0pts求条
1499743
ma_rui楼主2025/8/28 23:18

数据似乎过不了(下载样例)

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5+5,INF=0x3f3f3f3f,MOD=1e9+7;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef long long LL;
typedef struct node;
typedef node *tree;
struct node{
	int data,size;
	tree l,r;
};
tree root;
int t,op,x;
int lower(tree root){
	if(root){
		if(root->data<x)return 1+lower(root->l)+lower(root->r);
		else return lower(root->l);
	}else return 0;
}
int Find(tree root,int n){
	if(root->l&&root->r){
		if(n<=root->l->size)return Find(root->l,n-1);
		if(n==root->l->size+1)return root->data;
		return Find(root->r,n-root->l->size-1);
	}else if(root->l){
		if(n<=root->l->size)return Find(root->l,n-1);
		return root->data;
	}else if(root->r){
		if(n<=root->r->size)return Find(root->r,n-1);
		return root->data;
	}else return root->data;
}
int qq(tree root){
	if(root){
		if(root->data>=x)return qq(root->l);
		return min(root->data,qq(root->r));
	}else return 2147483647;
}
int hj(tree root){
	if(root){
		if(root->data<=x)return hj(root->r);
		else return max(root->data,hj(root->l));
	}else return -2147483647;
}
void insert(tree& root){
	if(root){
		if(root->data>x)insert(root->l);
		else insert(root->r);
	}else root = new node,root->data = x,root->size = 1,root->l = root->r = NULL;
	int cnt=1;
	if(root->l)cnt+=root->l->size;
	if(root->r)cnt+=root->r->size;
	root->size = cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>t;
	while(t--){
		cin>>op>>x;
		if(op==1)cout<<lower(root)+1<<endl;
		else if(op==2)cout<<Find(root,x)<<endl;
		else if(op==3)cout<<qq(root)<<endl;
		else if(op==4)cout<<hj(root)<<endl;
		else insert(root);
	}
	return 0;
}

2025/8/28 23:18
加载中...