题解

采用 "维护有序数组 + 模拟局部调整" 的策略，避免了每次查询都重新排序，大幅提升了效率。

---

整体思路

核心思想：始终保持数组 a[] 是"稳定排序后"的状态
          用 pos[id] 记录每个原始位置 id 当前在有序数组中的位置

修改操作：更新值 → 模拟冒泡排序的"局部调整" → 更新pos映射
查询操作：O(1) 直接查 pos[x]

---

逐段代码详解

1. 数据结构定义

const int N = 8005;
int n, q;

struct node {
    int id, value;  // id：原始位置编号，value：数值
};
node a[N];  // 始终维护为"稳定排序后"的数组
int pos[N]; // pos[id] = 原始位置id的元素，当前在有序数组中的位置

关键设计：

• a[] 数组始终按稳定排序规则有序
• pos[] 是反向映射：通过原始位置快速找到有序数组中的下标

---

2. 比较函数（保证稳定性）

bool cmp(node a, node b) {
    if(a.value != b.value) 
        return a.value < b.value;  // 值小的在前
    else 
        return a.id < b.id;        // 值相等时，原始位置小的在前
}

为什么这样写能保证稳定性？

情况	比较结果	排序后相对位置
a.value < b.value	true	a 在 b 前面 ✓
a.value > b.value	false	b 在 a 前面 ✓
a.value == b.value 且 a.id < b.id	true	a 在 b 前面 ✓
a.value == b.value 且 a.id > b.id	false	b 在 a 前面 ✓

✅ 值相同时，原始位置小的排前面 → 完全模拟题目中插入排序的稳定性！

---

3. 初始化：建立有序状态

cin >> n >> q;
for(int i = 1; i <= n; i++) {
    cin >> a[i].value;
    a[i].id = i;  // 记录原始位置
}
sort(a + 1, a + n + 1, cmp);  // 初始稳定排序
for(int i = 1; i <= n; i++) 
    pos[a[i].id] = i;  // 建立反向映射

执行后状态：

• a[1..n]：按稳定规则排好序
• pos[id]：原始位置 id 的元素现在在 a[] 的哪个下标

示例：

输入：n=3, 数组[3,2,1]
初始a[]: [{id:3,val:1}, {id:2,val:2}, {id:1,val:3}]
pos[]:   pos[1]=3, pos[2]=2, pos[3]=1

---

4. 处理操作

🔹 修改操作 op==1

if(op == 1) {
    cin >> v;
    a[pos[x]].value = v;  // 步骤1：找到位置x的元素，更新其值
    
    // 步骤2：向前冒泡（类似插入排序的"向左插入"）
    for(int j = pos[x]; j >= 2; j--) {
        if(cmp(a[j], a[j-1])) {  // 如果a[j]应该排在a[j-1]前面
            swap(a[j], a[j-1]);   // 交换
        }
    }
    
    // 步骤3：向后冒泡（处理可能向右移动的情况）
    for(int j = pos[x]; j < n; j++) {
        if(cmp(a[j+1], a[j])) {  // 如果a[j+1]应该排在a[j]前面
            swap(a[j+1], a[j]);   // 交换
        }
    }
    
    // 步骤4：更新pos映射（因为元素位置可能变了）
    for(int i = 1; i <= n; i++) 
        pos[a[i].id] = i;
}

为什么需要"向前+向后"两次冒泡？

因为修改后的值可能比原来更大或更小：

情况	示例	需要调整方向
值变小	[..., 5, 10, 15, ...] → 把10改成3	向前冒泡：3要移到5前面
值变大	[..., 5, 10, 15, ...] → 把10改成20	向后冒泡：20要移到15后面
值不变	无需移动	两次循环都会立即退出

模拟示例：

初始有序数组: [1(id:3), 2(id:2), 3(id:1)]
pos[]: pos[1]=3, pos[2]=2, pos[3]=1

操作: 1 3 2  (把原始位置3的元素值从1改为2)

步骤1: a[pos[3]]=a[1].value=2
       数组变为: [2(id:3), 2(id:2), 3(id:1)]  ← 可能无序！

步骤2: 向前冒泡 (j=1, j>=2不成立，跳过)

步骤3: 向后冒泡:
       j=1: cmp(a[2],a[1]) → cmp({id:2,val:2}, {id:3,val:2})
            值相等，比较id: 2<3 → true → 交换
            数组: [2(id:2), 2(id:3), 3(id:1)]
       j=2: cmp(a[3],a[2]) → cmp({id:1,val:3}, {id:3,val:2})
            3>2 → false → 不交换

步骤4: 更新pos[]: pos[1]=3, pos[2]=1, pos[3]=2

最终: a[] = [2(id:2), 2(id:3), 3(id:1)]  ← 稳定有序 ✓

🔹 查询操作 op==2

else if(op == 2) {
    cout << pos[x] << endl;  // O(1) 直接输出
}

原理：pos[x] 始终记录原始位置 x 的元素在当前有序数组中的下标。

---

---

总结

1. 稳定排序的cmp写法：值相等时按原始位置排序
2. 反向映射pos[]：用空间换时间，查询O(1)
3. 局部冒泡调整：修改后只需调整受影响的部分，不用全排
4. 及时更新映射：每次调整后必须同步更新pos[]

---

如果还是不理解，记住这三句话：

1. a[] 永远有序：像维护一个"实时排序"的数组
2. pos[] 是快捷方式：不用遍历找元素，直接查表
3. 修改=更新+局部调整：只动"受影响"的部分，类似插入排序的思想

类比理解：这就像维护一个"实时排行榜"，有人分数变了，只需把他往前/往后挪到正确位置，不用重新排整个榜！
用额外空间（pos数组）和局部调整，换取查询效率的大幅提升