7333.[CSP-J2021]插入排序

算法思路

1. 问题分析

题目要求维护一个数组，支持两种操作：修改元素值和查询元素在插入排序后的位置。核心挑战在于高效处理最多5000次修改和200,000次查询操作。直接每次查询都进行插入排序（O(n²)）会超时，需要设计更优的数据结构。

2. 解决策略

• 排序维护：使用结构体数组同时存储元素值和原始下标，按值（主序）和原始下标（次序）排序
• 位置映射：建立t[]数组记录每个原始下标在排序后的位置
• 修改优化：当修改元素值时：
  1. 定位该元素在排序数组中的位置
  2. 更新值后向前扫描调整位置（类似插入排序前移）
  3. 向后扫描确保有序性（类似插入排序后移）
  4. 重建位置映射表t[]
• 查询操作：直接通过t[]数组O(1)返回结果

3. 复杂度分析

• 时间复杂度：
  • 初始排序：O(n log n)
  • 修改操作：O(n)（最坏情况遍历整个数组）
  • 查询操作：O(1)
  • 总复杂度：O(n log n + 5000×n + Q)
• 空间复杂度：O(n)（存储排序数组和位置映射）
• 依据：修改操作上限5000次，n≤8000，5000×8000=40e6操作量可接受

代码实现

C++解法

cpp
复制
1#include<iostream>
2#include<algorithm>
3using namespace std;
4const int MAXN = 8005;
5
6struct Node {
7    int val;  // 元素值
8    int id;   // 原始下标
9};
10
11Node a[MAXN];  // 排序数组
12int t[MAXN];   // 位置映射: t[i]表示原始下标i在排序数组中的位置
13int n, q;
14
15// 比较函数：值升序，值相同时按原始下标升序
16bool cmp(Node x, Node y) {
17    if (x.val != y.val) return x.val < y.val;
18    return x.id < y.id;
19}
20
21int main() {
22    scanf("%d%d", &n, &q);
23    // 初始化排序数组
24    for (int i = 1; i <= n; i++) {
25        scanf("%d", &a[i].val);
26        a[i].id = i;
27    }
28    
29    // 初始排序 O(n log n)
30    sort(a + 1, a + n + 1, cmp);
31    
32    // 建立位置映射
33    for (int i = 1; i <= n; i++) {
34        t[a[i].id] = i;  // 记录原始下标对应的排序位置
35    }
36    
37    // 处理操作
38    while (q--) {
39        int opt, x, v;
40        scanf("%d", &opt);
41        if (opt == 1) {  // 修改操作
42            scanf("%d%d", &x, &v);
43            int pos = t[x];      // 获取当前排序位置
44            a[pos].val = v;      // 更新元素值
45            
46            // 向前扫描调整 O(n)
47            for (int j = pos; j >= 2; j--) {
48                if (cmp(a[j], a[j - 1])) {  // 若需要交换
49                    swap(a[j], a[j - 1]);   // 交换相邻元素
50                } else break;               // 已有序则终止
51            }
52            
53            // 向后扫描调整 O(n)
54            for (int j = pos; j < n; j++) {
55                if (cmp(a[j + 1], a[j])) {  // 若需要交换
56                    swap(a[j], a[j + 1]);   // 交换相邻元素
57                } else break;               // 已有序则终止
58            }
59            
60            // 重建位置映射 O(n)
61            for (int i = 1; i <= n; i++) {
62                t[a[i].id] = i;  // 更新所有元素位置
63            }
64        } 
65        else {  // 查询操作 O(1)
66            scanf("%d", &x);
67            printf("%d\n", t[x]);
68        }
69    }
70    return 0;
71}

代码解释：

1. 数据结构：
   • Node结构体存储元素值和原始下标
   • 数组a[]维护排序后的序列
   • 数组t[]建立原始下标到排序位置的映射
2. 核心操作：
   • 修改操作：定位→更新值→双向扫描调整位置→重建映射
   • 查询操作：直接通过t[]返回结果
3. 关键逻辑：
   • 比较函数cmp确保排序稳定性（值相同时按原始下标排序）
   • 双向扫描模拟插入排序的局部调整
   • 修改后重建映射保证位置信息正确性
4. 边界处理：
   • 扫描时检查边界（j>=2和j<n）
   • 遇到有序位置立即break优化性能

Python3解法

python
复制
1def main():
2    import sys
3    input = sys.stdin.read
4    data = input().split()
5    
6    # 解析输入数据
7    idx = 0
8    n = int(data[idx]); q = int(data[idx+1]); idx += 2
9    arr = list(map(int, data[idx:idx+n])); idx += n
10    
11    # 初始化排序数组：存储(值, 原始下标)
12    sorted_arr = [(val, i+1) for i, val in enumerate(arr)]
13    sorted_arr.sort(key=lambda x: (x[0], x[1]))  # 按值和原始下标排序
14    
15    # 建立位置映射表：t[i]表示原始下标i的排序位置
16    t = [0] * (n + 1)
17    for pos, (_, orig_idx) in enumerate(sorted_arr, start=1):
18        t[orig_idx] = pos
19    
20    # 处理查询
21    output = []
22    for _ in range(q):
23        opt = int(data[idx]); idx += 1
24        if opt == 1:  # 修改操作
25            x = int(data[idx]); v = int(data[idx+1]); idx += 2
26            pos = t[x] - 1  # 转Python索引（从0开始）
27            sorted_arr[pos] = (v, x)  # 更新值
28            
29            # 向前扫描调整 O(n)
30            for j in range(pos, 0, -1):
31                # 比较当前元素和前一个元素
32                cur_val, cur_id = sorted_arr[j]
33                prev_val, prev_id = sorted_arr[j-1]
34                # 若需要交换（值更小，或值相等但id更小）
35                if cur_val < prev_val or (cur_val == prev_val and cur_id < prev_id):
36                    sorted_arr[j], sorted_arr[j-1] = sorted_arr[j-1], sorted_arr[j]
37                else:
38                    break
39            
40            # 向后扫描调整 O(n)
41            for j in range(pos, len(sorted_arr)-1):
42                # 比较当前元素和后一个元素
43                cur_val, cur_id = sorted_arr[j]
44                next_val, next_id = sorted_arr[j+1]
45                # 若需要交换（值更大，或值相等但id更大）
46                if cur_val > next_val or (cur_val == next_val and cur_id > next_id):
47                    sorted_arr[j], sorted_arr[j+1] = sorted_arr[j+1], sorted_arr[j]
48                else:
49                    break
50            
51            # 重建位置映射 O(n)
52            for pos, (_, orig_idx) in enumerate(sorted_arr):
53                t[orig_idx] = pos + 1  # 位置从1开始计数
54        else:  # 查询操作 O(1)
55            x = int(data[idx]); idx += 1
56            output.append(str(t[x]))
57    
58    sys.stdout.write("\n".join(output))
59
60if __name__ == "__main__":
61    main()

代码解释：

1. 与C++实现的差异：
   • 使用元组(value, id)替代结构体
   • Python索引从0开始，需转换位置计算
   • 显式实现比较逻辑（无独立cmp函数）
2. Python特性利用：
   • sys.stdin.read()批量读取输入提升效率
   • 列表推导式初始化数据结构
   • 元组交换实现元素位置调整
3. 关键逻辑解析：
   • 比较逻辑：显式检查值和id的双重条件
   • 位置调整：双向扫描中实时比较相邻元素
   • 边界处理：循环范围控制（range(pos,0,-1)）
4. 性能优化：
   • 批量读写减少IO开销
   • 遇到有序位置立即终止扫描

复杂度对比

场景选择建议：

1. 竞赛场景：首选C++实现，尤其n接近8000时
2. 小规模数据：Python更易实现（n≤300）
3. 内存敏感：双语言空间复杂度相同
4. 可读性优先：选择Python实现（如教学场景）

效率差异根源：

1. C++的swap()操作和内存访问效率更高
2. Python动态类型和解释执行带来额外开销
3. 在5000×8000量级的操作中，C++比Python快5-10倍