你好！我是你的OI教练。

这道题（CSP-J 2021 T2）考察的是对排序稳定性的理解，以及根据数据范围选择合适算法的能力。

如果直接按照题目描述，每次操作都重新排序，肯定会超时。我们需要寻找一种更高效的维护方式。

下面我为你梳理一下解题的思路：

1. 深入理解“插入排序”与“稳定性”

题目给出的插入排序代码有一个关键细节：

if (a[j] < a[j-1]) { ... swap ... }

只有当后面的数严格小于前面的数时才交换。这意味着，如果两个数的值相等，它们的位置不会交换。

• 结论：这是一个稳定排序。
• 排序规则：
  1. 优先比较数值（数值小的排前面）。
  2. 如果数值相等，比较原始下标（原始下标小的排前面）。

2. 突破口：数据范围的暗示

请仔细看数据范围：

• $n \le 8000$
• $Q \le 2 \times 10^5$
• 修改操作（类型 1）不超过 5000 次。

这是一个非常强烈的信号：

• 查询操作（类型 2）非常频繁：必须在 $O(1)$ 或 $O(\log n)$ 的时间内完成。这意味着我们必须维护一个现成的“排名表”，不能每次查询都去遍历。
• 修改操作（类型 1）比较稀疏：允许使用 $O(n)$ 的时间来处理一次修改。

3. 核心策略：维护有序数组 + 映射数组

我们需要维护两个核心数据结构：

1. 结构体数组 p[n]：存储排序后的结果。每个元素包含两个属性：{val, id}（数值，原始下标）。
2. 反向索引数组 pos[n]：这是一个“传送门”。pos[x] 表示原始下标为 x 的那个元素，现在跑到了排序数组 p 的第几个位置。

算法流程：

Step 1: 初始化

• 读入数据，构建结构体数组 p。
• 使用 std::sort 对 p 进行排序。注意自定义比较函数：先比 val，val 相等比 id。
• 遍历排序后的 p，根据 p[i].id 填充 pos 数组：pos[p[i].id] = i。

Step 2: 处理修改操作 (1 x v)

• 找到它：通过 pos[x] 立刻知道这个元素在有序数组 p 中的位置，假设是 k。
• 修改它：把 p[k].val 修改为新的值 v。
• 调整位置（冒泡）：修改后，数组可能不再有序了。但因为只改了一个数，它离正确的位置不远。
  • 如果改大了：它需要往后移。和右边的邻居比，如果比邻居大（或者值相等但 id 比邻居大），就交换，直到位置正确。
  • 如果改小了：它需要往前移。和左边的邻居比，如果比邻居小（或者值相等但 id 比邻居小），就交换。
  • 关键点：每次交换 p[i] 和 p[j] 时，记得同步更新 pos 数组！
• 复杂度：最坏情况是这个数从头跑到尾，复杂度 $O(n)$。5000 次修改总共约 $4 \times 10^7$ 次运算，完全能过。

Step 3: 处理查询操作 (2 x)

• 直接输出 pos[x]。
• 复杂度：$O(1)$。

4. 代码结构提示

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Element {
    int val; // 数值
    int id;  // 原始下标
};

// 排序规则：值不同比值，值相同比下标
bool cmp(const Element &a, const Element &b) {
    if (a.val != b.val) return a.val < b.val;
    return a.id < b.id;
}

int n, Q;
Element a[8005]; // 排序数组
int pos[8005];   // 映射数组: pos[原下标] = 排序后现在的排名

int main() {
    // 1. 输入处理
    cin >> n >> Q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].id = i;
    }

    // 2. 初始排序
    sort(a + 1, a + 1 + n, cmp);
    
    // 3. 初始化 pos 映射
    for (int i = 1; i <= n; i++) {
        pos[a[i].id] = i;
    }

    // 4. 处理操作
    while (Q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v;
            cin >> x >> v;
            
            // 找到原下标为 x 的元素在排序数组中的位置
            int k = pos[x]; 
            a[k].val = v; // 修改数值

            // 向后冒泡 (变大了)
            // 只要 k 不是最后一个，且当前元素比后面的大(或者不满足稳定性)，就交换
            while (k < n && cmp(a[k+1], a[k])) {
                // 交换 a[k] 和 a[k+1]
                // 记得同时维护 pos 数组！
                swap(pos[a[k].id], pos[a[k+1].id]); // 先交换映射
                swap(a[k], a[k+1]);                 // 再交换实体
                k++;
            }
            
            // 向前冒泡 (变小了)
            // 只要 k 不是第一个，且当前元素比前面的小，就交换
            while (k > 1 && cmp(a[k], a[k-1])) {
                swap(pos[a[k].id], pos[a[k-1].id]);
                swap(a[k], a[k-1]);
                k--;
            }

        } else {
            int x;
            cin >> x;
            // O(1) 输出
            cout << pos[x] << endl;
        }
    }
    return 0;
}

易错点

1. 比较函数：一定要严格遵循题目定义的稳定性（值相同，id 小的在前）。冒泡调整的时候也要用这个逻辑。
2. 同步更新：交换 a 数组元素的时候，千万别忘了交换 pos 数组里对应的值，否则索引就乱了。

加油！理清了这个“维护有序”的逻辑，这道题就不难了。