---

一、題目

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

題目描述

您需要寫一種數(shù)據(jù)結(jié)構(gòu)，來維護(hù)一些數(shù)（ 都是 $10^9$ 以內(nèi)的數(shù)字）的集合，最開始時(shí)集合是空的。其中需要提供以下操作，操作次數(shù) $q$ 不超過 $10^4$：

1. 查詢 $x$ 數(shù)的排名（排名定義為比當(dāng)前數(shù)小的數(shù)的個(gè)數(shù) $+1$。若有多個(gè)相同的數(shù)，應(yīng)輸出最小的排名）。
2. 查詢排名為 $x$ 的數(shù)。
3. 求 $x$ 的前驅(qū)（前驅(qū)定義為小于 $x$，且最大的數(shù)）。若未找到則輸出 $?2147483647$。
4. 求 $x$ 的后繼（后繼定義為大于 $x$，且最小的數(shù)）。若未找到則輸出 $2147483647$。
5. 插入一個(gè)數(shù) $x$。

輸入格式

第一行是一個(gè)整數(shù) $q$，表示操作次數(shù)。

接下來 $q$ 行，每行兩個(gè)整數(shù) $op,x$，分別表示操作序號以及操作的參數(shù) $x$。

輸出格式

輸出有若干行。對于操作 $1,2,3,4$，輸出一個(gè)整數(shù)，表示該操作的結(jié)果。

樣例 #1

樣例輸入 #1

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

樣例輸出 #1

2
3
1
5

基本思路：

• 題目中提到了集合、而且是維護(hù)一些數(shù)的集合，我想到了STL中的set(底層是平衡樹的一種),不過集合元素中右重復(fù)的元素，需要用到multiset，可以存放重復(fù)的元素并且時(shí)升序排序的。
• 對于操作1，查詢x的排名，應(yīng)為set不支持隨機(jī)訪問，所以需要從頭遍歷一個(gè)一個(gè)數(shù)，需要注意的是”有多個(gè)相同的數(shù)，應(yīng)輸出最小的排名“，所以遍歷到第一個(gè)等于x的數(shù)break即可。
• 操作2，同1，遍歷集合。
• 操作3，再找前驅(qū)和后繼之前需要初始化一下multiset ，給出一個(gè)邊界。找x的前驅(qū)，用到了STL自帶的二分查找lower_bound，返回第一個(gè)大于等于x的迭代器。
• 操作4，使用upper_bound，返回第一個(gè)大于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數(shù)的排名int num=0;for(auto i:s)if(i<x) num++;//注意是<else break;cout<<num<<endl;}else if(op==2){//查詢排名為x的數(shù)int num=-1;for(auto i:s){num++;if(num==x){cout<<i<<endl;break;}}}else if(op==3){//x的前驅(qū)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;
}