P7910 [CSP-J 2021] 插入排序 二分题解
YoungL
·
·
题解
P7910 [CSP-J 2021] 插入排序 二分题解
原题传送门
题意很简单，就不废话了。
题解
而题目要我们求某个数是在排序后数组的第几位，这不就是二分模板题吗。
提交之后，很好，WA 了。
为什么呢？
插入排序是个稳定的排序方法
注意，我们要求的这个 “排名” 还需要考虑相同数下标间的关系，比如：
这个数组排序之后就是 $ {2, 2, 3} $。
还是那句话，**插入排序是个稳定的排序方法**，所以，我们这里要查找的是第二个 2，也就是排序后数组的第二个 2。(*这句话是核心，如果没看懂可以多读几遍。*)
那我们应该怎样判断下标呢？答：**结构体**。
```cpp
struct number {
int x, i; // x记录值，i记录下标
};
```
然后，我们还需要写出判断的函数（重载运算符）：
```cpp
bool operator<(const number& a, const number& b) {
return a.x == b.x ? a.i < b.i : a.x < b.x;
}
```
完成后，进行下一步。
#### 我们可以选择两种做法：
- 自己写二分
- lower_bound 大法
在这里，我们选用 lower_bound。
接下来的就很简单了，修改就 lower_bound 先删除旧的，添加新，查找就直接搜就行了。
#### 最后，注意一下细节：
- 选用 vector
- lower_bound 后要 - vec.begin() + 1（输出下标从1开始，vector 从0开始）
- 数组开足够大
这样，查询操作是 $ O(\log n) $ 的，修改操作是 $ O(n) $ 的（insert、erase 的复杂度），而修改操作不超过 5000 次，不会超时。
空间复杂度：$ O(n) $。
跑得还是挺快的，最慢的也就[60ms](https://www.luogu.com.cn/record/148272622)。
# 代码
```cpp
// Created by YoungL
#include <bits/stdc++.h>
// 不使用 using namespace std 是个好习惯
const int MAX_N = 2e5 + 5; // 其实8005就够了
int n, Q;
struct number { int x, i; } a[MAX_N]; // 带下标的数
std::vector<number> vec;
// 重载运算符
bool operator<(const number& a, const number& b) {
return a.x == b.x ? a.i < b.i : a.x < b.x;
}
#define OJ
signed main() {
// 比赛的时候要写freopen啊
#ifndef OJ
freopen("sort.in", "r", stdin);
freopen("sort.out", "w", stdout);
#endif
scanf("%d%d", &n, &Q);
for (int i=1; i<=n; i++) {
int x;
scanf("%d", &x);
vec.push_back(a[i] = (number){x, i}); // vector和a数组同时更新
}
std::sort(vec.begin(), vec.end()); // 对vector排序
for (int i=1; i<=Q; i++) {
int x, v, op;
scanf("%d%d", &op, &x);
if (op == 1) {
scanf("%d", &v);
vec.erase(std::lower_bound(vec.begin(), vec.end(), a[x])); // 先删除
a[x].x = v; // 修改
vec.insert(std::lower_bound(vec.begin(), vec.end(), a[x]), a[x]); // 再插入
}
else {
printf("%lld\n", std::lower_bound(vec.begin(), vec.end(), a[x])-vec.begin()+1); // 记得+1，因为下标原因
}
}
// fclose是个好习惯
#ifndef OJ
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
```