[CSP-J 2021] 插入排序

GitHub 跳转原题关系图返回列表

利用插入排序的稳定性维护按 (值, 原下标) 排序的普通数组，通过二分查找回答排名。

OJ: luogu

题目 ID: P7910

难度:普及/提高-

标签:排序模拟思维cspjpython

日期: 2026-06-19 03:08

题意

给一个数组，要支持两种操作：

修改 a[x] = v；
假设现在对整个数组执行题目给出的插入排序，询问“原下标为 x 的这个元素”最终会排在第几位。

注意这里问的是“元素的位置”，不是“值的位置”。

如果有多个相同的值，它们仍然要按照原下标区分。

思路

先看最直接的办法：每次查询时都把当前数组复制出来，真的执行一遍题目里的插入排序，再去找原下标 x 的元素最后在哪里。

这个版本最容易理解：

cpp

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

struct Node {
    int val;
    int id;
};

int n, q;
int a[MAXN];
Node b[MAXN];

int query_rank(int x) {
    for (int i = 1; i <= n; i++) {
        b[i].val = a[i];
        b[i].id = i;
    }

    // 真的按题目的插入排序伪代码做一遍，利用“<”保证稳定性。
    for (int i = 1; i <= n; i++) {
        for (int j = i; j >= 2; j--) {
            if (b[j].val < b[j - 1].val) {
                swap(b[j], b[j - 1]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (b[i].id == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x, v;
            cin >> x >> v;
            a[x] = v;
        }
        else {
            int x;
            cin >> x;
            cout << query_rank(x) << '\n';
        }
    }

    return 0;
}

但这样一次查询就是 $O(n^2)$ ，显然扛不住。

关键：这个插入排序是稳定的

题目里的交换条件是：

a[j] < a[j-1]

只有严格小于才交换，所以当两个数相等时，它们不会互换位置。

这就说明：相等元素的相对顺序不会变，也就是这个排序是稳定排序。

那么最终结果就不必再从“插入排序过程”去看，而可以直接改写成：

把每个元素看成二元组 (a[i], i)，然后按这个二元组升序排序。

原因很直接：

值小的元素一定在前面；
值相同的元素，因为稳定性，原下标小的仍然在前面。

所以查询 2 x 的答案，其实就是 (a[x], x) 在所有二元组里的排名。

方案二：维护有序数组 + 二分

维护一个普通数组 ord，其中按顺序保存当前所有二元组 (a[i], i)：

text

1ord[p] = 稳定排序后位于第 p 名的元素

初始化时，把所有二元组放入 ord[1..n]，再用 std::sort 排序。

查询

对于操作 2 x，在 ord 中二分查找 (a[x], x)。因为原下标属于二元组的一部分，每个二元组都是唯一的，所以二分找到的位置就是答案。

一次查询的复杂度是 $O(\log n)$ 。

修改

对于操作 1 x v：

二分找到旧二元组 (a[x], x)；
把它后面的元素向左移动一位，删除旧二元组；
更新 a[x] = v；
在剩余的 $n-1$ 个二元组中二分新插入位置；
把插入位置之后的元素向右移动一位，放入 (v, x)。

二分只需要 $O(\log n)$ ，但普通数组的移动需要 $O(n)$ ，所以一次修改的复杂度是 $O(n)$ 。题目保证修改次数不超过 $5000$ ，这个复杂度可以通过。

这个方案直接维护稳定排序后的完整顺序，思路和代码都比较直观。

cpp

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-12 17:56
 * update_at: 2026-07-12 17:56
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8000 + 5;

struct Node {
    int value;
    int id;
};

int n, q;
int a[MAXN];      // a[i] 表示原下标 i 的元素当前值
Node ord[MAXN];   // ord[pos] 表示稳定排序后第 pos 个元素

bool node_less(const Node &x, const Node &y) {
    if (x.value != y.value) {
        return x.value < y.value;
    }
    return x.id < y.id;
}

// 在 ord[1..len] 中找到第一个不小于 target 的位置。
int lower_bound_pos(const Node &target, int len) {
    int left = 1;
    int right = len;
    int answer = len + 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (!node_less(ord[mid], target)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}

// 删除旧二元组，再把新二元组插入有序数组。
void modify_value(int x, int value) {
    Node old_node;
    old_node.value = a[x];
    old_node.id = x;

    int old_pos = lower_bound_pos(old_node, n);
    for (int i = old_pos; i < n; i++) {
        ord[i] = ord[i + 1];
    }

    a[x] = value;
    Node new_node;
    new_node.value = a[x];
    new_node.id = x;

    int new_pos = lower_bound_pos(new_node, n - 1);
    for (int i = n; i > new_pos; i--) {
        ord[i] = ord[i - 1];
    }
    ord[new_pos] = new_node;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ord[i].value = a[i];
        ord[i].id = i;
    }
    sort(ord + 1, ord + n + 1, node_less);

    while (q--) {
        int op, x;
        cin >> op >> x;

        if (op == 1) {
            int value;
            cin >> value;
            modify_value(x, value);
        } else {
            Node target;
            target.value = a[x];
            target.id = x;
            cout << lower_bound_pos(target, n) << '\n';
        }
    }

    return 0;
}

方案一：直接维护排名数组

还可以不保存完整的有序序列，只用 rank_pos[i] 表示原下标为 i 的元素当前排在第几位。

初始化时，把所有元素存入 Node 数组并按 (a[i], i) 排序。排在第 p 位的结点，其原下标为 id，于是：

text

1rank_pos[id] = p

查询 2 x 时直接输出 rank_pos[x]，单次查询是 $O(1)$ 。

修改时，先记下 x 的旧排名。删除旧二元组后，原来排在它后面的元素都向前移动一位：

text

1如果 rank_pos[i] > old_rank，就令 rank_pos[i]--

然后更新 a[x] = v，并重新比较 (a[x], x) 与其它每个 (a[i], i)：

如果 (a[i], i) < (a[x], x)，说明元素 i 排在 x 前面，rank_pos[x] 加一；
否则 x 会插在元素 i 前面，rank_pos[i] 加一。

扫描一遍以后，所有元素重新得到正确排名。一次修改是 $O(n)$ ，一次查询是 $O(1)$ 。

cpp

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-19 22:27
 * update_at: 2026-07-12 16:35
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8000 + 5;

struct Node {
    int value;
    int id;
};

int n, q;
int a[MAXN];          // a[i] 表示原下标 i 的元素当前值
int rank_pos[MAXN];   // rank_pos[i] 表示元素 i 稳定排序后的当前排名
Node nodes[MAXN];     // 初始化时用于按 (值, 原下标) 排序

bool node_less(const Node &x, const Node &y) {
    if (x.value != y.value) {
        return x.value < y.value;
    }
    return x.id < y.id;
}

// 初始化每个原下标对应的稳定排序排名。
void init_rank() {
    sort(nodes + 1, nodes + n + 1, node_less);
    for (int i = 1; i <= n; i++) {
        rank_pos[nodes[i].id] = i;
    }
}

// 把元素 x 从旧排名中删除，再按新值插入到正确排名。
void modify_value(int x, int value) {
    int old_rank = rank_pos[x];

    // 删除旧元素后，排在它后面的元素都向前移动一位。
    for (int i = 1; i <= n; i++) {
        if (i != x && rank_pos[i] > old_rank) {
            rank_pos[i]--;
        }
    }

    a[x] = value;
    rank_pos[x] = 1;

    // 按 (值, 原下标) 比较，确定新元素的排名并调整后继元素。
    for (int i = 1; i <= n; i++) {
        if (i == x) {
            continue;
        }

        if (a[i] < a[x] || (a[i] == a[x] && i < x)) {
            rank_pos[x]++;
        } else {
            rank_pos[i]++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nodes[i].value = a[i];
        nodes[i].id = i;
    }
    init_rank();

    while (q--) {
        int op, x;
        cin >> op >> x;

        if (op == 1) {
            int value;
            cin >> value;
            modify_value(x, value);
        } else {
            cout << rank_pos[x] << '\n';
        }
    }

    return 0;
}

Python 知识

Python 元组按 (值, 原下标) 字典序比较，恰好表达稳定排序后的元素身份。
bisect_left 在 $O(\log n)$ 查到旧元素或查询排名。
insort 和 list.pop 的元素搬移由底层连续数组完成；题目限制修改不超过 5000 次，适合这种写法。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import sys
from bisect import bisect_left, insort


data = iter(map(int, sys.stdin.buffer.read().split()))
n, queries = next(data), next(data)
values = [next(data) for _ in range(n)]
ordered = sorted((value, index) for index, value in enumerate(values))
answers = []

for _ in range(queries):
    operation, index = next(data), next(data) - 1
    if operation == 1:
        new_value = next(data)
        ordered.pop(bisect_left(ordered, (values[index], index)))
        values[index] = new_value
        insort(ordered, (new_value, index))
    else:
        answers.append(str(bisect_left(ordered, (values[index], index)) + 1))

print("\n".join(answers))

复杂度

设第一类修改操作共有 $M$ 次，题目保证 $M \le 5000$ 。两个方案的空间复杂度都是 $O(n)$ 。

Python 正解维护普通有序数组：初始化是 $O(n \log n)$ ，每次修改是 $O(n)$ ，每次查询是 $O(\log n)$ ，总时间复杂度为：

O(n \log n + Mn + Q \log n)

总结

这题真正要抓住的是“插入排序这里是稳定排序”。

一旦把这一点想清楚，问题就从“模拟插入排序过程”变成了维护二元组的有序关系。

方案二直接维护完整有序数组，用二分查找排名，最容易对应到排序结果；方案一只维护每个元素的排名，修改时线性调整，能把查询进一步降到 $O(1)$ 。

P7910 [CSP-J 2021] 插入排序

题目描述

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$ ，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

cpp

1
2
3
4
5
6
7for (int i = 1; i <= n; i++)
	for (int j = i; j >= 2; j--)
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}

这下面是 Pascal 的示范代码：

pascal

1
2
3
4
5
6
7
8for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$ ，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1~x~v$ ：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$ 。保证 $1 \le x \le n$ ， $1 \le v \le 10^9$ 。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

$2~x$ ：这是第二种操作，假设 H 老师按照上面的伪代码对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$ ，在排序后的新数组所处的位置。保证 $1 \le x \le n$ 。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$ 。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

输入格式

第一行，包含两个正整数 $n, Q$ ，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$ 。

接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。

输出格式

对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例解释 #1】

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 2, 1$ 。

在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 1, 2$ 。

注意虽然此时 $a_2 = a_3$ ，但是我们不能将其视为相同的元素。

【样例 #2】

见附件中的 sort/sort2.in 与 sort/sort2.ans。

该测试点数据范围同测试点 $1 \sim 2$ 。

【样例 #3】

见附件中的 sort/sort3.in 与 sort/sort3.ans。

该测试点数据范围同测试点 $3 \sim 7$ 。

【样例 #4】

见附件中的 sort/sort4.in 与 sort/sort4.ans。

该测试点数据范围同测试点 $12 \sim 14$ 。

【数据范围】

对于所有测试数据，满足 $1 \le n \le 8000$ ， $1 \le Q \le 2 \times {10}^5$ ， $1 \le x \le n$ ， $1 \le v,a_i \le 10^9$ 。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

测试点	$n \le$	$Q \le$	特殊性质
$1 \sim 4$	$10$	$10$	无
$5 \sim 9$	$300$	$300$	无
$10 \sim 13$	$1500$	$1500$	无
$14 \sim 16$	$8000$	$8000$	保证所有输入的 $a_i,v$ 互不相同
$17 \sim 19$	$8000$	$8000$	无
$20 \sim 22$	$8000$	$2 \times 10^5$	保证所有输入的 $a_i,v$ 互不相同
$23 \sim 25$	$8000$	$2 \times 10^5$	无

[CSP-J 2021] 插入排序

目录

题意

思路

关键：这个插入排序是稳定的

方案二：维护有序数组 + 二分

方案一：直接维护排名数组

Python 知识

代码

复杂度

总结