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

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

题目链接：https://www.luogu.com.cn/problem/T237469?contestId=68358

题目描述

您需要写一种数据结构，来维护一些数（ 都是 10^9109 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 qq 不超过 10^4104：

1. 查询 xx 数的排名（排名定义为比当前数小的数的个数 +1+1。若有多个相同的数，应输出最小的排名）。
2. 查询排名为 xx 的数。
3. 求 xx 的前驱（前驱定义为小于 xx，且最大的数）。若未找到则输出 -2147483647−2147483647。
4. 求 xx 的后继（后继定义为大于 xx，且最小的数）。若未找到则输出 21474836472147483647。
5. 插入一个数 xx。

输入格式

无

输出格式

无

输入输出样例

输入 #1复制

7 5 1 5 3 5 5 1 3 2 2 3 3 4 3

输出 #1复制

2 3 1 5
解题思路：
1.想到使用multimet
2.熟悉multiset的各个函数功能

参考代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>q;
int n,t,x,order;
int main()
{
q.insert( -2147483647);
q.insert( 2147483647);
scanf(%d,&n);
while(n--)
{
scanf(%d%d,&t,&x);
if(t==1)
{
auto it=q.lower_bound(x);
order=0;
for(auto i=q.begin();i!=it;i++,order++);

printf(%d\n,order);

}
else if(t==2)
{
order=-1;
for(int i:q)
if(++order==x)
printf(%d\n,i);
}
else if(t==3)
{
auto it=q.lower_bound(x);
printf(%d\n,*--it);
}
else if(t==4)
{
printf(%d\n,*q.upper_bound(x));
}
else
{
q.insert(x);

}
}
return 0;
}