关于P5076的一点小理解

[题目传送门](https://www.luogu.com.cn/problem/P5076)

---
## Part.-1(?). 闲话
看了一下很多大佬们的题解啊，都很多都用了
 `BST multiset 树堆` 
之类的高级玩意儿，但是我过于蒟蒻，因此看不懂那些题解。感谢老师和
~~（陪我打CS1.6的）~~
同学，我最终还是用了一种较为野鸡的方法
 $AC$ 
了这道题，就来分享一下自己的心得。

## Part.0.  思路

看到这道题时，我就想到了用
`vector` [^1]
来进行代码的实现。
题目中没有明说数组的取值范围 [^2]
， 用
`vector`
实在再合适不过了。
于是我搞出了这样一个东西：
```cpp
vector <int> v, id;
```
其中 `v` 是初始数组， `id` 是我们在进行1~4操作过程中调动的数组。

接下来就一个个看各项操作吧。

## Part.1. 主体

### I.操作1 给数求排名

> 1.定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$ 。查询数 $x$ 的排名。注意 $x$ 不一定在集合里。

好的，我们要求 $x$ 的排名，那干脆就加进原本的 `id` 数组好了（之后的步骤也会出现）。这里其实不用管去重的问题，把它 `sort` 一遍之后直接查询最前面一个就可以了。

代码实现也很简单：

```cpp
int j;
id = v;
id.push_back(x);
sort(id.begin(), id.end());
for(j = 0; j < id.size(); j++){
	if (x == id[j]){
		cout << j + 1 << endl;
		break;
	}
}	
```

第一个操作很简单就可以完成了。

### II.操作2 给排名求数

> 2.查询排名为 $x (x≥1)$ 的数。保证集合里至少有 $x$ 个数。

基本思路和操作1差不多，但是实现更简单了。
```cpp
id = v;
sort(id.begin(), id.end());
cout << id[x - 1] << endl;
```
到这里还是很简单吧？

### III.操作3 给数求前驱

> 3.求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $−2147483647$ 。

这个时候，我们要考虑去重的问题了，不然会有些小bug（自己卡过好几次了， `Subtest#1` 都没过）。
去重的话，我用了一个小巧可爱的 `flag` 来帮助我们。
去重实现：

```cpp
for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
if (!flag) id.push_back(x);
```
（这里我要解释一下，我在最开始写代码时把 `flag` 作为全局变量，所以截取的代码直接看会有点奇怪）

接下来就可以排序+查找了。
```cpp
sort(id.begin(), id.end());
for (j = 0; j < id.size(); j++){
	if (x == id[j] && j != 0){
		flag = 1;
		cout << id[j - 1] << endl;
		break;
	}
}
if (!flag) cout << -2147483647 << endl;
```
还是比较美观的。

### IV.操作4 给数求后继

> 4.求 $x$ 的后继（后继定义为大于 $x$ ，且最小的数）。若不存在则输出 $2147483647$ 。

基本思路和操作3一样，但是注意小细节。
去重同，排序同，查找要注意一下。
代码实现：
```cpp
for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
if (!flag) id.push_back(x);
flag = 0;
sort(id.begin(), id.end());
for (j = 0; j < id.size(); j++){
	if (x == id[j] && j != id.size() - 1){
		flag = 1;
		cout << id[j + 1] << endl;
		break;
	}
}
if (!flag) cout << 2147483647 << endl;
```
最难的操作3和4都这样水灵灵地搞完了。

### V.操作5 给数入数组

> 5.插入一个数 $x$ ，本题的数据保证插入前 $x$ 不在集合中。

这不用思考了吧？

```cpp
v.push_back(x);
```

## Part.2. $AC$ 代码

直接附上吧（饥渴难耐）
```cpp
#include "bits/stdc++.h"
using namespace std;
vector <int> v, id;
int q;
bool flag;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> q;
	for (int i = 1; i <= q; i++){
		int op, x;
		cin >> op >> x;
		if (op == 1){
			int j;
			id = v;
			if (id.size() == 0){
				cout << 1 << endl;
				continue;
			}
			id.push_back(x);
			sort(id.begin(), id.end());
			for(j = 0; j < id.size(); j++){
				if (x == id[j]){
					cout << j + 1 << endl;
					break;
				}
			}	
		}
		if (op == 2){
			id = v;
			sort(id.begin(), id.end());
			cout << id[x - 1] << endl;
		}
		if (op == 3){
			int j;
			id = v;
			flag = 0;
			if (id.size() == 0){
				cout << -2147483647 << endl;
				continue;
			}
			for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
			if (!flag) id.push_back(x);
			flag = 0;
			sort(id.begin(), id.end());
			for (j = 0; j < id.size(); j++){
				if (x == id[j] && j != 0){
					flag = 1;
					cout << id[j - 1] << endl;
					break;
				}
			}
			if (!flag) cout << -2147483647 << endl;
		}
		if (op == 4){
			int j;
			id = v;
			flag = 0;
			if (id.size() == 0){
				cout << 2147483647 << endl;
				continue;
			}
			for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
			if (!flag) id.push_back(x);
			flag = 0;
			sort(id.begin(), id.end());
			for (j = 0; j < id.size(); j++){
				if (x == id[j] && j != id.size() - 1){
					flag = 1;
					cout << id[j + 1] << endl;
					break;
				}
			}
			if (!flag) cout << 2147483647 << endl;
		}
		if (op == 5) v.push_back(x);
	}
	return 0;
}
```
如果你足够细心，你会发现我加了很多没必要的判空代码，就当防伪标记了吧（实际上是懒得改）

## Part.3. 总结

怎么说呢，这道题是绿题还是有原因的，但整体上不难，也很容易一题多解，像是我这种蒟蒻都可以用一些独特的方法来 $AC$ 这道题。

我的代码也可以进一步优化，像是前文说的`flag`、判空等等，也希望各位大佬指点。

最后，感谢你的阅读，谢谢！

（我要赶紧回去补`BST`了，再见）

[![](https://jrenc.azurewebsites.net/api/signature?code=zHZRCCItO-yB8t7d2KyitELFDwADnXIotkeeIQL3juyNAzFucnyrWA%3D%3D&name=thanks%20for%20reading%20%20%20%20%20%20%20%20by%20%40Xianzi_(591561)&animate=true&speed=2&color=darkcyan)](www.luogu.com/user/591561)

$$\color{white}{我是彩蛋}$$

---

[^1]: `vector` 为STL容器中的可变长度数组。\
 `vector <typedef> typename (N, i);` //建立一个元素类型为`tpedef`的可变长度数组`typename`，最开始有N个初始值为i的元素，N、i可省略。\
`typename.push_back(a);` //将元素 `a` 插入数组 `typedef` 的末尾并增加数组长度。\
 `typename.size();` //返回数组 `typename` 长度。\
 `typename.resize(n, m);` //重新调整数组大小为n，新增元素初始化为m，m可省略。

[^2]:其实后来发现
`操作次数q不超过 10e4
`
 ，顶多只有10000个数据，用普通的数组也可以，但是
 `vector`
 类型有更多的优点，见下文\
 补充：普通数组在提交时容易 $TLE$

正在渲染内容...