【数据结构1-2】P5076 普通二叉树（简化版）(c++，multiset做法)

本文主要是介绍【数据结构1-2】P5076 普通二叉树（简化版）(c++，multiset做法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、题目
【深基16.例7】普通二叉树（简化版）
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
  - 基本思路：

一、题目

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

题目描述

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

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

输入格式

第一行是一个整数 $q$ ，表示操作次数。

接下来 $q$ 行，每行两个整数 $o p, x$ ，分别表示操作序号以及操作的参数 $x$ 。

输出格式

输出有若干行。对于操作 $1, 2, 3, 4$ ，输出一个整数，表示该操作的结果。

样例 #1

样例输入 #1

样例输出 #1

基本思路：

题目中提到了集合、而且是维护一些数的集合，我想到了STL中的set(底层是平衡树的一种),不过集合元素中右重复的元素，需要用到multiset，可以存放重复的元素并且时升序排序的。
对于操作1，查询x的排名，应为set不支持随机访问，所以需要从头遍历一个一个数，需要注意的是”有多个相同的数，应输出最小的排名“，所以遍历到第一个等于x的数break即可。
操作2，同1，遍历集合。
操作3，再找前驱和后继之前需要初始化一下multiset ，给出一个边界。找x的前驱，用到了STL自带的二分查找lower_bound，返回第一个大于等于x的迭代器。
操作4，使用upper_bound，返回第一个大于x的迭代器，取值后即是x的后继。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1000010;
multiset<int> s; 
const int INF = 2147483647;void solve(){int op,x;cin>>op>>x;if(op==1){//查询x数的排名int num=0;for(auto i:s)if(i<x) num++;//注意是<else break;cout<<num<<endl;}else if(op==2){//查询排名为x的数int num=-1;for(auto i:s){num++;if(num==x){cout<<i<<endl;break;}}}else if(op==3){//x的前驱cout<<*(--s.lb(x))<<endl;}else if(op==4){//x的后继cout<<*(s.ub(x))<<endl;}else{//将x插入集合s.insert(x);}}signed main(){IOS;int T=1;cin>>T;s.insert(INF),s.insert(-INF);while(T--){solve();}return 0;
}