难度：困难。题目原型为洛谷 P7910 [CSP-J 2021] 插入排序。本题的考点是在线维护稳定排名：不重排，而是维护 rank[]，单点修改只影响 O(n) 个元素的名次。

目标

完成本题后，你应该能够：

• 定义「稳定排名」：a[i] 在稳定排序后位于第几名；
• 说明为什么不能每次操作都 O(n log n) 全排序（会超时）；
• 用 O(n) 更新受影响的排名、O(1) 回答查询。

前置知识

• 10.2 插入排序与「稳定」的含义；
• 10.3 用 (value, index) 二元组做稳定排序。

题目

给一个长度为 n 的数组 a[1..n]，支持 Q 次操作：

• 操作 1 x v：把 a[x] 改成 v；
• 操作 2 x：查询当前 a[x] 在「对当前数组做稳定排序」后的位置（第几名，从 1 起）。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数 a[1..n]；
• 第三行一个整数 Q；
• 接下来 Q 行，每行一个操作：1 x v 或 2 x。

输出格式

对每个 2 x 操作，输出一行整数表示 a[x] 的名次。

数据范围

项目	范围
数组长度 n	1 ≤ n ≤ 8000
操作次数 Q	1 ≤ Q ≤ 2 × 10⁵
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

3
2 1 3
4
2 2
1 2 4
2 1
2 3

样例输出

1
1
2

样例解释

初始 a = [2, 1, 3]，稳定排序为 [1, 2, 3]，所以 a[2] = 1 排第 1 名，输出 1。

把 a[2] 改成 4 后 a = [2, 4, 3]，稳定排序为 [2, 3, 4]：a[1] = 2 排第 1 名，输出 1；a[3] = 3 排第 2 名，输出 2。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-05-insertion-sort-update
pnpm lab:score -- labs/chapter-10/exercise/E-10-05-insertion-sort-update

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 含重复值（稳定性）、n=1、连续修改三种情况都通过
• 能说出「每次全排序 O(n log n)」在 n=8000、Q=2×10⁵ 时为什么超时

思考题

1. 为什么「稳定排名」必须同时比较 a[i] < v 和 a[i] == v 且 i < x？
2. 如果去掉「稳定」要求（相等元素顺序任意），名次还能唯一确定吗？

题解

点击查看题解

思路

元素 x 在稳定排序中的名次等于「排在它前面的元素个数 + 1」。元素 i 排在 x 前面当且仅当：

• a[i] < a[x]，或
• a[i] == a[x] 且 i < x（稳定性：相等时按下标先后）。

维护 rank[x] 表示当前名次：

1. 初始用 (a[i], i) 做一次稳定排序，得到每个位置的初始名次，O(n log n)；
2. 查询 2 x 直接输出 rank[x]，O(1)；
3. 修改 1 x v：把 a[x] 从 old 改为 v，只有两类元素受影响——
   • x 自己：新名次 = 1 +「值小于 v 的个数」+「值等于 v 且下标小于 x 的个数」；
   • 其它元素 i：看 x 在修改前后是否排在 i 前面，据此让 rank[i] 加一、减一或不变。

一次修改只需 O(n) 扫一遍数组。

复杂度分析

• 预处理：O(n log n)（一次稳定排序）；
• 每次修改：O(n)；
• 每次查询：O(1)；
• 总复杂度：O(n log n + n · Q)，对 n ≤ 8000、Q ≤ 2 × 10⁵ 可接受；
• 空间复杂度：O(n)。