3017: 【普及+/提高】【P5076】普通二叉树（简化版）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：1
题目描述
您需要写一种数据结构，来维护一些数（ 都是 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 不超过 ：
- 查询 数的排名（排名定义为比当前数小的数的个数 。若有多个相同的数，应输出最小的排名）。
- 查询排名为 的数。
- 求 的前驱（前驱定义为小于 ，且最大的数）。若未找到则输出 。
- 求 的后继（后继定义为大于 ，且最小的数）。若未找到则输出 。
- 插入一个数 。
输入
第一行是一个整数 ，表示操作次数。
接下来 行，每行两个整数 ，分别表示操作序号以及操作的参数 。
输出
输出有若干行。对于操作 ，输出一个整数，表示该操作的结果。
样例输入 复制
7
5 1
5 3
5 5
1 3
2 2
3 3
4 3样例输出 复制
2
3
1
5提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
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 rank1(int x,int root) { //查找数的排名
if(root)
{
if(x<t[root].value) //右子树所有数据都比x大，故进入左子树
return rank1(x,t[root].left);
if(x>t[root].value) //左子树所有数据都比x大，故进入右子树并且加上左子树的size
return rank1(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) { //查询排名为x的数
if (x<=t[t[root].left].size)
//排名为x的数在左子树，故进入左子树
return kth(x,t[root].left);
if (x<=t[t[root].left].size+t[root].num)
//当前根结点就是排名为x的数，返回当前根结点的值
return t[root].value;
return kth(x-t[t[root].left].size-t[root].num,t[root].right);
/*
排名为x的数在右子树，故进入右子树，并把x减去左子树size+t[root].num(根结点)
*/
}
void insert(int x,int &root) { //插入值为x的数
if (x<t[root].value) //插入到左子树中
if(!t[root].left)
//左儿子不存在，则新建一个权值为x的结点作为左儿子
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)
//右儿子不存在，则新建一个权值为x的结点作为右儿子
t[ t[ root ].right = ++cnt] =Node(0,0,1,x);
else //右儿子存在，则递归插入
insert(x,t[root].right);
else //x的结点已经存在，把结点大小加一
t[root].num++;
update(root);
}
int main(){
cin >> n;
int num = 0;
t[ root = ++cnt] = Node(0,0,1,2147483647);
while (n--) {
cin >> opt >> x;
num++;
if(opt == 1) cout << rank1(x,root) << endl;
else if(opt == 2) cout << kth(x,root) <<endl;
else if(opt == 3) cout << kth(rank1(x,root) - 1,root) <<endl;
else if(opt == 4) cout << kth(rank1(x+1,root),root) <<endl;
else num--,insert(x,root);
}
return 0;
}