本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-12 20:48:04

二叉搜索树？我为什么要用？
这道题是可以直接模拟的呀。
下面我们就来分析它的每一个操作：

1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。 查询 $x$ 的排名。
   由于集合中没有重复元素， 故可以直接使用 STL 中的 lower_bound()， 复杂度为 $O(\log_2n)$。
2. 查询排名为 $x(1\le x)$ 的数。
   直接调用，$O(1)$ 解决。
3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。 若不存在则输出 $-2147483647$。
   再次 lower_bound() 二分查找， 复杂度为 $O(\log_2n)$。
4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。 若不存在则输出 $2147483647$。
   upper_bound() 查找， 同上。
5. 插入一个数 $x$。
   先 lower_bound() 找出应插入的位置，再插入（用动态数组是因为不想手写 insert() 函数）， 复杂度为 $O(n)$。
   总体复杂度为 $O(n^2)$。
   代码：

#include<bits\/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF 2147483647
using namespace std;
vector<int>g;
int q,op,x;
inl int read(){
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}                
	return f*x;      
}                 
inl void write(int x){
	if(x<0){         
		x=-x;        
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
inl void solve(){
	reg int xx;
	op=read();
	x=read();
	switch(op){
		case 1:
			xx=lower_bound(g.begin(),g.end(),x)-g.begin();
			write(xx);
			putchar('\n');
			break;
		case 2:
			write(g[x]);
			putchar('\n');
			break;
		case 3:
			xx=lower_bound(g.begin(),g.end(),x)-g.begin();
			if(xx-1==g.end()-g.begin()||!(xx-1)) write(-INF);
			else write(g[xx-1]);
			putchar('\n');
			break;
		case 4:
			xx=upper_bound(g.begin(),g.end(),x)-g.begin();
			if(xx==g.end()-g.begin()) write(INF);
			else write(g[xx]);
			putchar('\n');
			break;
		case 5:
			g.insert(lower_bound(g.begin(),g.end(),x),x);
			break;
	}
	return;
}
signed main(){
	g.push_back(0);
	q=read();
	while(q--) solve();
	return 0;
}