四川新站优化,做网站资料,做网站什么公司好,手机网站制作流程图文章目录 一、题目【深基16.例7】普通二叉树#xff08;简化版#xff09;题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路#xff1a; 一、题目
【深基16.例7】普通二叉树#xff08;简化版#xff09;
题目描述
您需要写一种数据结构#xff0c;来维… 文章目录 一、题目【深基16.例7】普通二叉树简化版题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路 一、题目
【深基16.例7】普通二叉树简化版
题目描述
您需要写一种数据结构来维护一些数 都是 1 0 9 10^9 109 以内的数字的集合最开始时集合是空的。其中需要提供以下操作操作次数 q q q 不超过 1 0 4 10^4 104
查询 x x x 数的排名排名定义为比当前数小的数的个数 1 1 1。若有多个相同的数应输出最小的排名。查询排名为 x x x 的数。求 x x x 的前驱前驱定义为小于 x x x且最大的数。若未找到则输出 − 2147483647 -2147483647 −2147483647。求 x x x 的后继后继定义为大于 x x x且最小的数。若未找到则输出 2147483647 2147483647 2147483647。插入一个数 x x x。
输入格式
第一行是一个整数 q q q表示操作次数。
接下来 q q q 行每行两个整数 o p , x op,x op,x分别表示操作序号以及操作的参数 x x x。
输出格式
输出有若干行。对于操作 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4输出一个整数表示该操作的结果。
样例 #1
样例输入 #1
7
5 1
5 3
5 5
1 3
2 2
3 3
4 3样例输出 #1
2
3
1
5基本思路
题目中提到了集合、而且是维护一些数的集合我想到了STL中的set(底层是平衡树的一种),不过集合元素中右重复的元素需要用到multiset可以存放重复的元素并且时升序排序的。对于操作1查询x的排名应为set不支持随机访问所以需要从头遍历一个一个数需要注意的是”有多个相同的数应输出最小的排名“所以遍历到第一个等于x的数break即可。操作2同1遍历集合。操作3再找前驱和后继之前需要初始化一下multiset 给出一个边界。找x的前驱用到了STL自带的二分查找lower_bound返回第一个大于等于x的迭代器。操作4使用upper_bound返回第一个大于x的迭代器取值后即是x的后继。
#includebits/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 pairint,int PII;
const int N 1000010;
multisetint s;
const int INF 2147483647;void solve(){int op,x;cinopx;if(op1){//查询x数的排名int num0;for(auto i:s)if(ix) num;//注意是else break;coutnumendl;}else if(op2){//查询排名为x的数int num-1;for(auto i:s){num;if(numx){coutiendl;break;}}}else if(op3){//x的前驱cout*(--s.lb(x))endl;}else if(op4){//x的后继cout*(s.ub(x))endl;}else{//将x插入集合s.insert(x);}}signed main(){IOS;int T1;cinT;s.insert(INF),s.insert(-INF);while(T--){solve();}return 0;
}
