P7910. 插入排序

发表于 分类于 阅读次数： Waline： 本文字数： 341 阅读时长 ≈ 1 分钟

考点

  • 排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
// b数组的键为原下标，值为现下标；便于修改
int n, b[maxn];

struct node {
  int v_, idx_;
} a[maxn];

bool cmp(node &x, node &y) {
  if (x.v_ != y.v_) return x.v_ < y.v_;
  return x.idx_ < y.idx_;
}

void update(int x, int v) {
  x = b[x], a[x].v_ = v;
  while (x + 1 <= n && !cmp(a[x], a[x + 1])) swap(a[x], a[x + 1]), ++x;
  while (x - 1 >= 1 && !cmp(a[x - 1], a[x])) swap(a[x], a[x - 1]), --x;
  for (int i = 1; i <= n; ++i) b[a[i].idx_] = i;
}

void query(int x) { cout << b[x] << endl; }

int main() {
  int opt, x, v, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) a[i].idx_ = i, cin >> a[i].v_;
  sort(a + 1, a + 1 + n, cmp);
  for (int i = 1; i <= n; ++i) b[a[i].idx_] = i;
  while (q--) {
    cin >> opt;
    if (opt == 1) {
      cin >> x >> v;
      update(x, v);
    } else {
      cin >> x;
      query(x);
    }
  }
  return 0;
}

思路

本题主要难点在于两个：

  • 排序的优化

    如果每次都以\(O\left( n\log n \right)\)的时间复杂度去重新打乱排序，肯定炸了；

    但是如果是在有序数组内修改一个数，只需要用\(O\left( n \right)\)的打擂台方式就能将其换到合适的位置。

    （也就是题目说的插入排序....？这其实是冒泡不是吗....）

  • 样例的解读

    如果值不同，根据值从小到大排序；如果值相同，根据原本的下标序号从小到大排序。