拿到这道题的时候我正在CSP-J 2021复赛的考场上。看到题目名“插入排序”说实话心里先咯噔了一下不会要手写插入排序吧结果把题面读完才发现命题人完全不是这个意思。P7910这道题表面上顶着排序算法的名字实际核心是“维护一个有序序列”的模拟题考的是稳定排序的性质和倒序更新的思维。今天就把这道题的完整思路、代码、以及我在写题过程中踩过的坑一次性掰开揉碎讲清楚。这道题适合三类人看正在备考CSP-J/S的选手、学完排序算法想找点应用场景的同学以及那些被题目名字“骗”过、想彻底搞懂洛谷P7910的读者。不管你是刚入门还是刷题老手只要能把“稳定排序”这个概念吃透这道题的正解其实不难。1. 先说结论这题考的根本不是“插入排序”1.1 一道题名带“排序”却不用排序的题目P7910的题面大概是这样的给你一个长度为n的序列有q次操作。操作分两种第一种是“1 x v”把原数组中下标为x的元素的值改成v第二种是“2 x”询问原数组中下标为x的元素在把数组按从小到大排序之后排在第几位。这里有一个非常关键的限制条件如果两个元素的值相同那么排序后要按照它们在原数组中的先后顺序排列。换句话说这是一个“稳定排序”问题不是普通排序。很多同学看到题目名是“插入排序”下意识就开始回忆插入排序的模板代码想着每次修改完就插入一下。实际上这题的“插入排序”只是一个引子暗示你排序过程要稳定同时暗示你可以利用“大部分元素已经有序”这一点来做局部调整。真正要你实现的是一套能应付单点修改和排名查询的数据结构逻辑。1.2 数据范围才是解题的钥匙我们来看数据范围n和q都最多是8000。这个数字很有意思它既不算小到可以纯暴力也不算大到必须上高级数据结构。如果你每次都调用sort重排整个数组一次排序是O(n log n)q次操作就是O(nq log n)。8000 × 8000 × log8000约等于8.3亿次比较。在竞赛环境下这个数量级很危险很可能超时。但如果你能把单次操作的复杂度控制在O(n)甚至O(1)总复杂度就是O(nq) 6400万次操作。这个量级在C里是稳过的。所以数据范围告诉你这道题的正确姿势是“单次操作最多扫一遍数组”。2. 题面精读与关键性质提炼2.1 “稳定”两个字值千金题目里关于稳定排序的表述很多人一眼扫过去就忽略了。但这恰恰是整道题的核心。什么叫稳定排序就是值相等的元素在排序后保持它们原本的相对顺序。比如原数组是 [3, 1, 2]其中下标2和下标3的值分别是1和2没有重复。但如果有重复比如 [2(下标1), 1(下标2), 2(下标3)]稳定排序后应该是 [1(下标2), 2(下标1), 2(下标3)]值相同的2下标1仍然在下标3前面。这个性质直接决定了我们用什么排序规则。如果忽略稳定性直接用值排序那么查询时遇到相同的值你就不知道应该返回哪个排名了。在这道题里两个元素的值相同它们在有序数组中的先后完全由原下标决定。因此我们需要用一个结构体同时存“值”和“原数组下标”并按照“值优先、下标次之”的规则排序。2.2 两种操作到底在干什么操作1是单点修改把原数组第x个位置的值改成v。注意这里说的是“原数组下标”而不是有序数组中的位置。这意味着每次修改时我们需要快速定位这个元素现在在有序数组的哪个位置然后更新它的值。操作2是排名查询问原数组第x个位置的元素在稳定排序后排第几。注意返回的是“排名”也就是排序后它是第几个元素。如果我们始终维护着一个有序数组并且知道原数组每个元素在有序数组中的下标那么查询就是O(1)的事。所以整个题目的关键就变成了如何在修改一个元素的值之后用尽量快的速度让整个数组重新恢复成稳定排序状态。3. 核心思路从“每次排序”到“定向调整”3.1 为什么不能无脑sort我先说说我一开始的渣思路。第一次读完题我心想这题不就每次修改后sort一下然后查找吗写起来多快。但仔细一算如果8000次操作每次sort一遍8000个元素的数组复杂度接近8亿再加上查询时的扫描很容易在1秒时限的边缘疯狂试探。更麻烦的是每次sort会破坏有序数组与原数组下标的对应关系。你sort完还得重新记录每个原下标对应的新位置又是O(n)的开销。所以每次操作都sort的做法不仅慢写起来也啰嗦。正解思路应该是始终维护一个已经排好序的结构体数组。每次修改一个元素的值时由于它左右两侧的元素依然是有序的只需要把这个元素往左或往右“挪”到它应该在的位置即可。这个过程类似于一次冒泡但只针对一个元素最坏情况下扫一遍数组复杂度O(n)。3.2 用结构体数组保管“值原下标”具体来说我开一个结构体数组astruct Node { int val; // 元素值 int id; // 原数组下标 } a[8005];数组下标从1开始使用。初始时读入n个元素第i个元素的val就是读入的值id就是i。然后调用sort(a 1, a n 1, cmp)其中cmp的规则是先按val从小到大如果val相等按id从小到大。这一步就把“稳定排序”的结果准备好了。你可能会说题目不是叫“插入排序”吗怎么直接用sort了注意初始排序用什么算法都无所谓因为我们需要的是“排好序的结果”而不是排序的过程。直接sort只是预处理后续维护才是重点。排序完成后我们再开一个pos数组pos[i]表示“原数组下标为i的元素现在在有序数组a中的位置”。这一步是后面O(1)查询的关键。3.3 修改操作的双向冒泡式调整现在处理操作1也就是把原数组下标x的元素改成v。首先通过pos[x]找到这个元素在有序数组a中的位置p。然后把a[p].val改成v。此时整个数组可能不再有序但因为左右两边仍然分别有序所以这个元素只需要向左或向右移动就能让整个数组重新有序。如果这个元素的值变小了它应该往左移动。只要它比左边相邻的元素小或者值与左边元素相等但id更小稳定序要求它排前面就交换它们更新pos继续往前看。如果这个元素的值变大了它应该往右移动。只要它比右边相邻的元素大或者值与右边元素相等但id更大稳定序要求它排后面就交换它们更新pos继续往后看。这里有个细节你并不确定这个元素是变大了还是变小了所以稳妥的做法是先判断往左移动的条件能移就移等它稳定下来后再判断往右移动的条件能移就移。两个方向都处理一遍就能保证整个数组有序。为什么这样处理一定正确因为除了这个被修改的元素之外其他元素已经按照稳定排序规则有序排列。这个元素要么“插”到前面的合适位置要么“塞”到后面的合适位置不会影响其他元素之间的相对顺序。这正是插入排序的核心思想也是题目名字的由来。4. 参考代码与逐段拆解4.1 结构体定义与排序规则先给出完整的参考代码然后再逐段解释其中的关键细节。#include bits/stdc.h using namespace std; struct Node { int val, id; } a[8005]; int n, q; int pos[8005]; bool cmp(const Node x, const Node y) { if (x.val ! y.val) return x.val y.val; return x.id y.id; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n q; for (int i 1; i n; i) { cin a[i].val; a[i].id i; } sort(a 1, a n 1, cmp); for (int i 1; i n; i) { pos[a[i].id] i; } while (q--) { int op; cin op; if (op 1) { int x, v; cin x v; int p pos[x]; a[p].val v; while (p 1) { if (a[p].val a[p - 1].val || (a[p].val a[p - 1].val a[p].id a[p - 1].id)) { swap(a[p], a[p - 1]); pos[a[p].id] p; pos[a[p - 1].id] p - 1; p--; } else { break; } } while (p n) { if (a[p].val a[p 1].val || (a[p].val a[p 1].val a[p].id a[p 1].id)) { swap(a[p], a[p 1]); pos[a[p].id] p; pos[a[p 1].id] p 1; p; } else { break; } } } else { int x; cin x; cout pos[x] \n; } } return 0; }这段代码的核心一个是cmp函数一个是两个方向的while循环。cmp函数里“值相等时按id升序”体现了稳定排序while循环里“值相等时根据id决定是否交换”则是在动态维护稳定排序。4.2 修改操作为什么两个方向都要检查很多新手会问我先判断一次如果这个元素不需要往左移动那是不是直接往右移动就行其实不然。你无法预知修改后的值相对于左右邻居到底是变大还是变小所以稳妥的做法是先把往左能走的走完再把往右能走的走完。举个例子原数组是 [1, 4, 5, 2, 3]稳定排序后是 [1, 4, 2, 3, 5]这里id对应关系就不细写了。假设我们把下标5的元素值改成0这个元素突然变得特别小它需要一路移动到最前面。这时候左边的元素都比它大它自然会一路交换到最前面。反过来如果把一个本来在中间靠前的元素值改成100它需要一路往右移动。如果不检查向右的条件这个数组右半部分就不再有序。两个while循环虽然看起来像双重循环但注意每次交换后p都在变化整个元素只会沿着一个方向移动。最坏情况下一个元素从数组一头移动到另一头扫描n次所以单次修改是O(n)。整个程序复杂度是O(nq)完全可以在时间限制内跑完。4.3 查询操作pos数组才是真正的功臣每次查询只要输出pos[x]即可。因为pos数组记录的就是“原数组下标x的元素在有序数组中的位置”而这个位置就是它的排名。没有pos数组会怎样你得在有序数组里遍历一遍找到id等于x的那个元素输出它的下标。虽然也是O(n)但有了pos数组查询变成O(1)整个程序的耗时上限完全由修改操作决定。这就是典型的信息换时间多维护一个数组换来每次查询的常数时间。这个思路在后续做其他维护类题目时也非常常见。5. 常见错误与考场避坑实录5.1 忘了稳定排序的定义这是我身边朋友中招最多的地方。有人直接用pairint,int存pair默认排序是先比较first再比较second如果first相等就按second排。这实际上和“值优先、下标次之”的规则是一致的。但如果你手动写cmp一不小心写成了只按值比较那么相同值的元素在排序后顺序就不确定了后续查询结果就会错。检查方法很简单构造一组包含重复值的样例比如 [2, 1, 2]分别查询下标1和下标3的排名。如果两个查询结果是1和2说明稳定性保持住了如果出现其他结果就要检查cmp和两个while条件里的“值相等时按id比较”是否都写对了。5.2 修改后只往一个方向调整这个错法我自己也犯过。当时想的是先判断这个元素比左边大、比右边小那就不用动否则如果比左边小就往左移动。结果漏了“修改后的值变大了”的情况导致数组后半段乱掉。正确姿势是写完往左走的循环后再写一个往右走的循环。不要试图用if合并因为往左走完p的位置变了你还需要重新判断是否需要往右走。分开写最稳妥。5.3 pos数组没同步更新这个错属于“代码写出来看着没问题一跑样例就崩”的类型。如果你在swap两个元素之后只更新了值却没有更新pos数组中两个元素的新位置那么后续查询就会找错元素。我强烈建议养成习惯每次swap后立刻更新两个元素的pos。如果怕漏可以在swap后用注释标注“这行是同步更新pos”提醒自己。5.4 暴力sort能不能过有人可能会问我每次修改后直接stable_sort难道不行吗stable_sort本身能保证稳定排序复杂度是O(n log n)。8000次操作最坏大约是7.7亿次比较如果常数比较小、数据比较水也许能勉强卡过去。但那是在赌数据竞赛题目往往会有针对性数据稳妥做法还是写O(nq)的双向调整。还有同学想用树状数组或者权值线段树来维护排名但题目值域是1e9离散化后还要处理带修改、带稳定序的问题反而把简单题复杂化了。在n和q只有8000的前提下O(n)的单次修改已经是指数级优于暴力的方案。6. 从这道题能学到的竞赛思维6.1 别被题目名字带偏P7910这个题名放在考场上其实是一种心理博弈。看到“插入排序”很多选手会不由自主地把思维往“排序算法实现”上引从而忽略了题面真正要求的“维护有序序列”这个核心。这种情况在竞赛中特别常见比如有的题叫“最大公约数”实际考的是动态规划有的题叫“斐波那契”实际考的是矩阵快速幂。所以拿到题目先别被标题带着走。老老实实读题画样例抽象出“我到底要维护什么”再想用什么算法。6.2 排序稳定性也是一种“有序性”初学者往往把稳定性当作排序算法的一个无关紧要的属性考试时也经常忽略。但这道题告诉你稳定性可以成为解题的关键线索。它本质上说明元素之间的“先后关系”不只有值还有id。你可以把“稳定排序后的顺序”看作一个复合排序键(val, id)。一旦你建立了这个观念后续很多问题都会变得清晰交换条件、查询排名、重复值处理全部基于这个复合键。这也是为什么结构体自定义cmp比直接用两个数组更容易写对。6.3 进阶思考数据范围变大怎么办如果这道题的n和q都变成2e5那么O(nq)的做法就彻底挂了。你会需要更高级的数据结构比如用平衡树维护所有元素每个节点储存(val, id)查询时用节点编号计算排名或者离线后使用CDQ分治、整体二分等算法处理带修改的全局排名问题。但从入门组的角度看掌握O(nq)的双向调整已经足以拿到满分。我个人觉得做这道题最大的收获不是又背下来一个模板而是学会了“局部有序性”这个思想。很多看似需要重新排序的题目只要你能找到一个“不变量”把修改范围限制在一个小区域内就能把复杂度降下来。这种思维在后续做树状数组、平衡树、可持久化线段树的时候还会反复用到。最后再分享一个小技巧考场上一旦确定了O(nq)的思路不要急着写正解先写一个每次修改后用stable_sort的暴力代码用来对拍。然后生成随机小数据对比暴力代码和优化代码的输出是否一致。我用这个方法在两分钟内就抓到了自己“漏更新pos”的bug。如果你也在备战CSP强烈建议把对拍养成习惯。