6月GESP四级考完那天晚上几个学生在微信群里对答案聊到第二题排序时直接吵了起来。有人说直接调sort过样例很轻松有人说担心大数据会超时还有人连题目里“多次升序排序”到底该怎么理解都没绕明白。这个场景其实每年都在重演四级第二题看起来只是一道排序题考的却不是“你会不会sort”而是你能不能把题目讲清楚、把复杂度算明白、把边界写对。这篇文章我打算认真复盘一下这道题。先说明一点具体题面以官方为准以下内容是根据考生回忆和公开讨论整理的题目模型。题目大意是小杨有一个包含n个正整数的序列a他计划对序列进行多次升序排序操作每次操作会指定一个区间[l, r]把区间内的元素重新按升序排列最后输出完整序列。围绕这个模型我会把从暴力到优化的完整思路、参考代码、考场易错点都拆开讲一遍顺便聊聊这类题到底在筛选什么样的能力。1. 考后复盘这道排序题到底在考什么1.1 考后整理的题面模型结合多位考生的回忆这道题的核心可以整理成下面这个形式输入一个长度为n的正整数序列a下标从1开始。输入m表示小杨要做m次排序操作。每次操作给出两个整数l和r要求把a[l]到a[r]这一段按升序从新排列。所有操作按输入顺序执行最后输出整个序列。比如一个简单的演示数据5 2 3 1 4 2 5 1 5 2 4第一次把整个序列排序得到1 2 3 4 5第二次对区间[2,4]再排一次结果不变输出1 2 3 4 5。这个模型看起来很朴素但它把“排序”从一道记忆性的概念题变成了一道带场景的模拟题。考生需要做的第一件事不是写代码而是确认一点这些排序操作是分区间、按顺序执行的不是让你对全序列只排一次。很多人考后说题目简单其实就是因为他们把模型读成了“整体排序一次”代码自然好写而真正困难的点在于理解“多次”和“区间”这两个词叠加之后带来的复杂度问题。1.2 为什么“排序”题会出现在四级第二题GESP四级考纲里排序一直是很重要的考点。大纲要求学生掌握两类东西第一常见排序算法的原理、过程和时间复杂度第二在具体问题里正确选择排序方式。第二题安排在编程题的位置说明它既要考察算法的理解也考察实现能力。注意一个细节四级考试的第一题和第二题通常比第三题简单是“保分题”。所以这道排序题并不是用来刁难人的它的作用是筛选那些读题不仔细、复杂度不过脑子、边界条件随手写的考生。我见过太多学生在四级模拟卷上做类似题目时栽在了不读数据范围、不验证样例、输出格式出错这些看起来很低级的地方。真正把这道题做对的人往往不是算法最强的而是习惯最稳的。另外从备考角度看这道题背后还有一个隐藏考点你会不会用STL里的sort以及你会不会在不会优化的时候果断选择暴力。关于这一点我后面会详细讲。2. 第一版解法用std::sort暴力排序区间2.1 直接排序区间的写法如果只看题目模型最直接的想法是每读入一个区间[l, r]就用sort对这个区间排序。C里sort的区间是左闭右开的所以如果数组从1开始存代码是这样#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } while (m--) { int l, r; cin l r; if (l r) swap(l, r); if (l r) continue; sort(a.begin() l, a.begin() r 1); } for (int i 1; i n; i) { if (i 1) cout ; cout a[i]; } cout \n; return 0; }这段代码可以拿来做两个验证一是用题目样例测试逻辑二是用小规模随机数据和自己手推的结果对比。很多同学不敢在考场上用sort总觉得手写快排更“正统”其实完全没必要。C标准库的sort是经过优化的混合排序平均表现远好于大部分人手写的版本而且GESP考试环境允许使用C标准库。四级阶段的编程题能用STL就要大胆用省下来的时间可以用来检查边界条件。2.2 复杂度的账要算清楚暴力解法能不能过完全取决于n和m的数据范围。每次操作区间长度为lensort一次的时间大约是O(len log len)。如果m次操作都接近整个序列的长度那总时间大约是O(m n log n)。假设n 10^5m 10^5这个复杂度基本不可能在2秒内跑完。但如果n和m都只有几千这个写法就是完全可靠的。GESP四级的第二题通常不会用极限数据去卡纯暴力因为它的定位是基础题。问题是很多考生不会主动去估算复杂度看到排序就直接写也不管数据范围。我建议拿到题第一步先看输入规模养成这个习惯能让很多问题提前暴露。你自己心里要先有一个预期这个题是允许O(n^2)还是必须O(n log n)分析清楚了再决定用哪种写法。另外还应该想清楚一个特殊情况如果某次操作的区间长度是1比如l等于r那排序前后没有任何变化。代码里如果不对l r做特判sort一个长度为1的区间虽然不报错但属于无意义的系统调用在m特别大的时候会白白消耗时间。这种细节就是区分满分和99分的地方。3. 从超时教训看正解的关键观察3.1 大量排序操作是冗余的如果数据一加大纯sort区间的写法就有风险。但在升级算法之前必须先想明白一个问题什么样的排序操作是真正必要的有一个很容易观察到的性质一个区间如果已经严格升序那么对它做升序排序不会产生任何变化。换句话说如果某次操作给定的区间内部本来就没有逆序对这次操作就可以直接跳过。怎么快速判断一个区间是否有逆序对可以用前缀和。定义一个标记数组bad[i]当a[i - 1] a[i]时bad[i] 1否则为0。那么区间[l, r]内部严格递增的条件是下标从l1到r的所有bad值全部为0。也就是bad[l 1] bad[l 2] ... bad[r]等于0。为了O(1)得到这个区间和可以维护一个前缀和数组preBad。preBad[i]表示bad[1]到bad[i]的和。区间内逆序标记之和就是preBad[r] - preBad[l]。注意这里用的是preBad[r]减去preBad[l]正好把bad[l]排除掉因为bad[l]描述的是a[l - 1]和a[l]之间的关系不属于[l, r]内部。有了这个判断就能在排序之前先检查一次。如果区间本身有序直接continue如果无序才执行sort。这个优化实现成本很低但对重复排序同一段数据的测试点效果非常明显。3.2 排序完成后有序信息会变化跳过一个已经有序的区间很容易但真正的难点在另一个地方每次排序完成后整个数组相邻元素之间的有序关系会改变之前维护的bad数组和preBad前缀和必须同步更新。排序操作对bad数组的影响可以分成三部分区间内部因为排序后是升序所以区间内部相邻元素都满足a[i - 1] a[i]也就是从bad[l 1]到bad[r]全部变成0。左边界a[l - 1]和新的a[l]之间的顺序可能改变所以bad[l]要重新计算。右边界a[r]和新的a[r 1]之间的顺序可能改变所以bad[r 1]要重新计算。这个更新步骤特别容易漏。我见过有人写出了“跳过有序区间”的优化但忘记在sort之后更新bad数组结果第一次排序后所有有序判断全部错乱程序输出乱七八糟。所以如果要在代码里维护这样的前缀信息一定要把“排序影响哪些标记”当成一道独立的小题来仔细处理。3.3 进一步的思考合并区间与整体排序还有一个更宏观的观察如果多个操作区间可以互相覆盖甚至嵌套那么一个覆盖范围更大的排序操作往往会让后续更小的操作变成多余的。比如先对[1, 10]排序再对[3, 7]排序第二次操作实际上不会改变任何东西因为整个[1, 10]已经有序了子区间当然也有序。顺着这个想法有人会尝试把所有区间合并成一个或几个“有效大区间”只对这些大区间排序。这个思路在部分测试点上是对的但要注意两个问题如果操作顺序是交错的比如先排[1, 5]再排[4, 8]这两个区间部分重叠合并成一个[1, 8]后直接排序得到的结果不一定和“按顺序执行两次”相同。因为第二次排序用到了第一次排序后的中间状态而不是原始状态。区间覆盖关系必须结合原始序列的内容判断不是单纯从区间端点就能确定的。所以在四级阶段我不建议在考场上做过于复杂的区间合并。比较稳妥的做法是先写一个带有序跳过的暴力sort版本如果题目数据真的很大再根据题目的特殊限制去寻找更高级的数据结构方案。4. 参考实现完整C代码与逐段解析4.1 带有序跳过的优化版实现下面这个版本把上一节的两个关键点都实现了排序前检查区间是否有序排序后正确更新bad和preBad数组。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n 2); for (int i 1; i n; i) { cin a[i]; } // bad[i] 1 表示 a[i-1] a[i] vectorint bad(n 2, 0), preBad(n 2, 0); for (int i 2; i n; i) { bad[i] (a[i - 1] a[i]) ? 1 : 0; preBad[i] preBad[i - 1] bad[i]; } auto rebuild [](int l, int r) { // 区间排序后内部逆序标记全部为0 for (int i l 1; i r; i) { bad[i] 0; } // 左边界a[l-1] 与 a[l] if (l 2) { bad[l] (a[l - 1] a[l]) ? 1 : 0; } // 右边界a[r] 与 a[r1] if (r 1 n) { bad[r 1] (a[r] a[r 1]) ? 1 : 0; } // 重新构造前缀和从 l 开始向后更新即可 for (int i max(2, l); i n; i) { preBad[i] preBad[i - 1] bad[i]; } }; while (m--) { int l, r; cin l r; if (l r) swap(l, r); if (l r) continue; // 如果区间内部已经严格递增排序是无效操作直接跳过 int insideReversed preBad[r] - preBad[l]; if (insideReversed 0) { continue; } sort(a.begin() l, a.begin() r 1); rebuild(l, r); } for (int i 1; i n; i) { if (i 1) cout ; cout a[i]; } cout \n; return 0; }4.2 逐段理解代码里的处理逻辑第一遍看代码可能会觉得rebuild函数很乱我拆开解释一下。先看bad数组的意义。bad[i]只描述一对相邻位置的关系a[i - 1]是否大于a[i]。注意它不包含a[i]和a[i 1]的关系那个是bad[i 1]的事。所以区间[l, r]内部相邻关系对应的下标是l 1到r一个不多一个不少。排序完[l, r]之后区间内部的所有相邻对都变成升序所以bad[l 1]到bad[r]可以安全地设为0。但是l和r这两个位置是区间的“切口”它们和外部的邻居a[l - 1]、a[r 1]的关系发生了变化必须用当前的数值重新判断。把这三部分处理完bad数组就反映了最新的数组状态。再说preBad的更新。排序只可能改变下标l以及l之后所有前缀和的值因为影响点集中在l、l 1到r、r 1这些位置。理论上影响点之后的所有preBad都可能变化所以循环从max(2, l)更新到n是安全的。l之前的前缀和不受影响不需要动。这个写法的复杂度是O(n - l)比纯暴力sort在随机数据下多了一些开销但换来了跳过大量冗余sort的能力整体上通常划算。4.3 一个走查示例拿这组数据走一遍6 3 2 1 3 4 6 5 1 2 3 4 5 6初始数组是2 1 3 4 6 5bad数组bad[2] 1因为2 1bad[3] 0因为1 3bad[4] 0因为3 4bad[5] 0因为4 6bad[6] 1因为6 5第一次操作[1,2]preBad[2] - preBad[1] 1说明有逆序执行sort得到1 2 3 4 6 5。rebuild后bad[2]变成0bad[3]还是0。第二次操作[3,4]区间内是3和4已经有序insideReversed为0跳过。第三次操作[5,6]区间内是6和5有逆序sort后变成5 6最终输出1 2 3 4 5 6。这个例子简单但很能说明问题如果所有操作都是对有序小区间进行的裸sort会白白做很多次无意义的排序而带跳过逻辑的程序能直接识别并快速通过。练习时可以自己多构造几组包含重复区间、包含逆序数据的数据来验证。5. 考场易错点清单与样例验证方法5.1 下标和区间边界的经典翻车现场这道题最大的坑不是算法而是下标。很多考生习惯从0开始存数组读入区间[l, r]后直接用sort(a.begin() l, a.begin() r 1)但题目如果明确说从1开始就容易出现错位。我的建议是解这类题统一从1开始存让数组下标和题目描述完全一致省去换算的烦恼。这样sort的区间仍然要记得“左闭右开”所以结束位置要加1写成a.begin() r 1。有一个细节值得单独说如果输入的l大于r要不要处理从题目描述看正常数据不会出现l r但为了保险我在代码里做了swap。这个习惯能防止那些手滑造数据的测试点代价只是一行代码值得写。5.2 输出格式和读入优化GESP的判题对输出格式要求很严格多一个空格通常不会判错但少一个换行可能出问题。最稳妥的做法是数字之间用空格分隔整个序列输出完毕后单独输出一个换行。我写代码时习惯用cout并且用if判断避免行尾多一个空格。读入优化方面如果数据量达到十万级别建议加上ios::sync_with_stdio(false)和cin.tie(nullptr)。这两行能让cin的读入速度提升很多。一些人认为GESP不考大数据不需要这些但加上没有任何坏处养成习惯就好。5.3 样例验证与自造数据的思路样例通过只能说明逻辑方向对不能说明性能够。我的习惯是写完之后再自造三组数据第一组m次操作全部覆盖整个序列验证多次整体排序会不会出错。第二组区间长度全是1或者l等于r验证临界分支是否正确。第三组逆序序列配合嵌套区间例如先排[1, n]再排[2, n - 1]这种数据最容易暴露bad数组更新遗漏的问题。你甚至可以写一个简单的对拍程序一个文件放纯暴力sort版本一个文件放优化版随机生成数据比较两份输出是否一致。我在带学生准备GESP时经常让他们做这个练习因为对拍能一次性验证所有想不到的边界情况。5.4 什么时候该放弃优化写暴力这是考场上一个很现实的问题。我的建议是如果你无法在几分钟内确定正解就写暴力版本至少保证基础分。GESP四级第二题作为基础题纯sort的暴力写法在温和数据下完全能拿满分。在考场上最怕的不是暴力超时而是你花了四十分钟憋一个不成熟的优化结果代码写错连暴力分都拿不到。这里有一个适用场景的分层参考n和m都很小几千以内直接sort区间不需要任何优化。n较大但m较小先把每次操作读进来判断其中有没有明显冗余的区间再决定是否用优化版。n和m都很大需要从题目本身的特殊限制出发找区间排序的等价性质通常涉及分块、平衡树一类的手段这已经超出大部分四级考生的范围。6. 从这道题反推四级备考重点6.1 排序理论不能只会背结论GESP四级考察排序不只是问快排的时间复杂度是多少而是会给你一个具体场景让你在场景里判断用什么方式实现。所以备考时不要只背结论一定要亲手写一遍冒泡、选择、插入、快排和归并。写完之后再用STL的sort做对比观察不同排序在相同数据下的行为差异。还有一个经常被忽略的点是排序的稳定性。虽然这道题用sort不会涉及稳定性但四级笔试选择题里出现过稳定性的概念辨析。建议把稳定排序和不稳定排序各记几个典型例子并且知道为什么选择排序不稳定、为什么归并排序稳定。这些理论最终都会在编程题的场景里以变体的形式出现。6.2 复杂度直觉比模板重要做这类题最关键的能力是“看一眼数据范围就大概知道算法能不能过”。我常用一个粗略标准一秒内C可以跑大约10^7到10^8次简单运算。如果复杂度到了10^9基本就可以判定需要优化。平时刷题时每做完一题都把时间复杂度和空间复杂度写下来然后和输入规模对照这个习惯会极大提升考场上的判断速度。6.3 训练读题和样例检查的肌肉记忆最后想说一件听起来很基础但特别重要的事把题目读完整把样例自己手推一遍。很多考生看到“排序”两个字就兴奋直接开始敲代码结果题目中某些操作细节理解错了等写完才发现样例输出都对不上。我在文章里整理的题目模型只是便于讨论的版本你真正上考场时要以试卷原题的文字描述为准。这类题的读题顺序建议是先看输入输出格式再看数据范围最后看操作规则。操作规则里如果出现“多次”“每次”“区间”这类词就要想一想这些操作之间有没有依赖关系、会不会互相影响。想清楚了再动手写代码会顺畅很多。我个人的实际感受是GESP四级第二题往往不是决定你能不能过级的题而是检验你基础习惯的题。真正能稳定拿高分的考生不是那些会背各种高级算法的选手而是那些读题仔细、复杂度清楚、边界条件一个不漏的“稳”人。把这篇文章里的代码和易错点吃透再自己动手在编辑器里把两种版本都敲一遍这个考点对你来说就不会再是扣分项了。