相邻交换排序的最小次数：逆序对与归并排序、树状数组解法

看到这个题号很多刷题的老哥应该都不陌生。1618这道“排牌牌”名字起得挺有生活气息仿佛就是打牌的时候把乱牌一张张捋顺。但等你真上手写代码就会发现这题根本不是让你模拟“捋牌”它考的是你能不能把一个看似模拟的过程看穿成离散数学里的经典量——逆序对。这篇文章不打算只贴一份AC代码就完事我会从题目背后的逻辑开始讲把为什么答案是逆序对数、归并排序怎么数、树状数组怎么数、以及我实际提交时踩过的坑全部摊开说适合刚接触逆序对的初学者也适合想彻底搞懂“相邻交换排序”这类模型的同学。1. 先看懂“排牌牌”在问什么1.1 题面到底长什么样我没法保证每个OJ上的题面一字不差但核心规则通常是这样的有N张牌牌面上写着1到N这N个数字因为洗牌洗得比较狠所以数字整体是乱的。现在定义一次操作挑任意两张相邻的牌交换它们的位置。问最少需要多少次操作才能让所有牌从左到右按数字从小到大排好。注意几个关键词相邻交换、升序排列、最小次数。这三个条件叠在一起基本就能锁定考点了。如果题目说“可以交换任意两张牌”那是另一个模型后面我会展开讲。这里说的“排牌牌”绝大多数版本就是相邻交换。N的范围我没有必要瞎编一个精确值但这类题给到1e5甚至1e6都很正常反正直接模拟一定过不了。我第一次看到这题的时候脑子里第一个想法就是冒泡排序从左往右扫遇到逆序就交换顺便计数扫到没有逆序为止。对小数据这当然没问题可一旦N是十万量级O(N^2)的冒泡就是灾难1e10量级的操作在1秒时限下完全没有生还的可能。所以这题一定不是让你去真的“排牌”而是要你找到某个能直接计算出答案的数学量。1.2 关键观察相邻交换能改变什么让我们把问题抽象一下。给定一个排列也就是一个长度为N的数组目标是从小到大有序。定义“逆序对”为一对下标ij、但a[i]a[j]的位置。在升序排列里逆序对数量是0一个完全降序的排列逆序对数量最大是N*(N-1)/2。现在看一次相邻交换到底会产生什么影响。假设我们要交换位置k和k1上的两个数也就是相邻的两个元素。交换之后这两个数和它们前后所有元素之间的相对位置关系其实都没变变的只是这两个元素之间的先后顺序。如果原来a[k]a[k1]这两个元素构成一个逆序对交换后它们变成有序逆序对数量减少1。如果原来a[k]a[k1]交换后逆序对数量反而增加1。也就是说任何一次相邻交换最多只能让整体逆序对数量减少1。而我们的目标状态逆序对数量是0所以从初始状态到目标状态至少需要初始逆序对数那么多次操作。这个下界能不能达到能。只要序列还没完全升序就必然存在至少一对相邻的逆序对因为如果所有相邻位置都升序整个序列就升序了。那么我们每次都找一对相邻逆序对交换每步都能让逆序对数量减1一直减到0为止。所以“最少操作次数初始逆序对数量”这个结论就是从这两个方向夹出来的。这个推导过程建议大家自己动手写一遍哪怕是用小例子比如[3,1,2]或[2,3,1]逐个画一下交换过程体会一次交换只影响一对相邻元素这件事。想清楚这一层题目就从“模拟题”变成了“计数题”。2. 怎么数逆序对归并排序与树状数组2.1 归并排序求逆序对的原理既然答案是逆序对数接下来问题就变成怎么在O(N log N)时间内数出逆序对。最常见的做法是归并排序。它的核心思想是分治把数组从中间分成左右两半分别递归求出左半内部的逆序对数、右半内部的逆序对数然后在合并左右两半的时候数出所有“横跨左右”的逆序对。合并过程本身就是把两个已经有序的子数组合并成一个有序数组。假设左半边从i到mid右半边从j到r。当右半边的当前元素a[j]小于左半边的当前元素a[i]时这里就产生了一大批逆序对因为左右两半各自有序左半边从i到mid的所有元素全都比a[j]大而且它们在原数组里的位置都在a[j]之前。因此逆序对数量要加上(mid-i1)。反过来如果左半边的a[i]小于等于右半边的a[j]则没有逆序对产生直接照常放入合并数组。在代码层面归并排序统计逆序对特别自然只需要在“取右半边元素”的那个分支里加一句计数就行。我直接把常用模板贴出来注释都写清楚方便对着看。#include bits/stdc.h using namespace std; int n; int a[100005]; int tmp[100005]; long long ans 0; // 答案必须是 long long void mergeSort(int l, int r) { if (l r) return; int mid (l r) 1; mergeSort(l, mid); mergeSort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { // a[j] 比 a[i] 小说明左半边从 i 到 mid 都和 a[j] 构成逆序对 tmp[k] a[j]; ans (long long)(mid - i 1); } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) { a[p] tmp[p]; } } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); } mergeSort(1, n); printf(%lld\n, ans); return 0; }关于“a[i] a[j]”这个判断有个细节要不要取等号。如果题目规定牌面是1到N的排列没有重复数字取不取等号其实不影响计数因为相等的情况不存在。但如果你在练习题或变体里遇到有重复值的序列那么等于的情况一定不能算作逆序对。使用等于时优先取左半边的元素能保证统计不漏也不多。从稳定性角度说归并排序本身是一个稳定排序用是符合稳定排序语义的。2.2 树状数组求逆序对的思路另一个高效方案是树状数组。它的思路比归并排序更接近“计数”本身我们不看元素大小而是把数组当成一个桶统计每个数值已经出现了多少次。假设我们从右往左扫描原数组。对于当前扫到的元素x所有已经扫过的元素都在x的右边。如果其中有些元素比x小那么它们和x就能构成逆序对。于是只要查询一下“数值区间[1, x-1]里已经插入了多少个数”再把这个数量累加到答案里然后把x也插入桶中。这个过程用树状数组可以做到单次操作O(log N)总体O(N log N)。那为什么需要离散化因为如果牌面上的数字范围很大比如大到1e9我们不可能开一个1e9大小的数组。离散化的思想是把所有数字排序并去重然后用数字在排序数组中的排名来代表它本身。这样值域被压缩到N以内树状数组的下标就够用了。#include bits/stdc.h using namespace std; const int MAXN 100005; int n; int a[MAXN]; int c[MAXN]; vectorint sorted; int lowbit(int x) { return x (-x); } void add(int p, int v) { for (; p n; p lowbit(p)) { c[p] v; } } int query(int p) { int res 0; for (; p 0; p - lowbit(p)) { res c[p]; } return res; } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); sorted.push_back(a[i]); } sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int i 1; i n; i) { a[i] lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() 1; } long long ans 0; for (int i n; i 1; --i) { ans query(a[i] - 1); add(a[i], 1); } printf(%lld\n, ans); return 0; }这段代码里最容易被忽略的是离散化后的下标从1开始。tree数组天然要求下标从1起否则add和query里的lowbit循环会出问题。lower_bound返回的是0-based下标一定要加1。这个1我见过的初学同学里至少有一半会在这里WA一次包括我自己当年也是提交上去错得莫名其妙半天才发现下标越界或查询范围不对。后面我专门列一个踩坑清单。2.3 归并排序和树状数组怎么选很多同学会纠结这两种都能过到底写哪种好我直接给结论看数据范围和你的熟练度。归并排序的好处是不用考虑值域数组多大都能跑而且分治过程天然稳定对重复元素的处理很直观。缺点是代码量稍长而且它是递归的如果你是那种写递归容易晕的人调试起来可能费点劲。树状数组的代码量更短逻辑更“在线”一旦你会背模板写起来非常快。但它的前提是要做离散化而且如果题目数据里有重复值你需要想清楚查询范围是query(a[i]-1)还是query(n)-query(a[i])两个方向都能得到正确答案但写错一个就全盘皆输。从运行常数来说归并排序通常比树状数组快一些因为树状数组每次查询和修改都要走一遍lowbit路线常数比较大。不过在1e5量级这点差距完全感知不到到了1e6量级两者也都还能压进时限。我的习惯是如果这道题我还要顺手复现一下稳定排序就写归并如果只是想快速交掉就写树状数组。两种都练熟以后遇到逆序对变体才不会慌。3. 从“排牌牌”往外看不同玩法对应不同结论3.1 看清操作类型比背结论重要“排牌牌”这类题最大的迷惑性在于名字太像模拟以至于很多人一上来就手写冒泡。其实排序类问题的算法选择几乎完全由“操作类型”决定。操作类型一变答案模型就完全不一样。如果操作是交换相邻元素最小次数等于逆序对数。这正是本题。如果操作是交换任意两张牌结论就变成了N减去置换环的个数。如果操作是抽出一张牌再插入到任意位置结论又变成了N减去最长上升子序列长度。为什么相邻交换对应逆序对因为一次相邻交换只改变一对元素的相对顺序等于每次只能消除一个逆序对。而任意交换为什么对应置换环因为你可以把任意两个位置的数直接互换那么一个长度为k的置换环内部只需要k-1次交换就能全部归位。抽出插入为什么对应最长上升子序列因为不动的牌必须保持原有相对顺序而且数值要递增能够“原地不动”的最多那批牌恰好就是原序列中的一个最长上升子序列。3.2 举个小例子感受置换环模型假设数组是[2,3,1]目标升序是[1,2,3]。如果允许任意交换那么2应该在位置23应该在位置31应该在位置1。把每个元素当前所在位置映射到它应该去的位置会得到一个环位置1上的2要去位置2位置2上的3要去位置3位置3上的1要去位置1这三个位置构成一个三元素环。一个长度为k的环只需要k-1次交换就能恢复所以这个例子需要2次交换。你可以试一试确实两次就能排好。再比如[2,1,4,3]它有两个二元素环每个环需要1次交换总共2次。这就是“N减置换环数”的含义每个长度为k的环只需要k-1次操作把N个元素所在的环加起来就是N减去环的个数。3.3 再看抽出插入模型如果操作是“抽一张牌出来插入到任意位置”那你想想看哪些牌可以完全不动它们在被抽插的过程中保持相对位置不变并且最终必须有序所以它们在原序列里本身就是按数值递增的相对顺序出现的。这正好是LIS的定义。假设原序列是[3,1,2,4]LIS是[1,2,4]或[1,2,3]长度为3那么把3拿出来插到末尾一步就排好了。答案就是N-LIS。很多同学刷题久了容易把结论背死看到“最小交换次数”就套逆序对。这里我真心建议每碰到一道题先圈出“每次操作可以做哪件事”再决定套哪个模型。三步走先把操作翻译成数学变化再想这个变化量每步最多能减少多少最后找数据结构实现计数。这个方法能覆盖一大类排序问题。4. 完整AC代码与提交时的细节4.1 归并排序版本完整程序把代码放一起方便直接复制调试。要注意的就是数组大小一定开够下标从1开始。如果题目数据到1e6数组还要再开大一点不能刚好卡在1e5。#include bits/stdc.h using namespace std; const int MAXN 100005; int n; int a[MAXN], tmp[MAXN]; long long ans; void mergeSort(int l, int r) { if (l r) return; int mid (l r) 1; mergeSort(l, mid); mergeSort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { tmp[k] a[j]; ans (long long)(mid - i 1); } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) { a[p] tmp[p]; } } int main() { while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) { scanf(%d, a[i]); } ans 0; mergeSort(1, n); printf(%lld\n, ans); } return 0; }这个版本支持多组输入每次循环前把ans清零。递归函数里没有依赖全局状态的坑所以多组数据也能直接跑。如果你的OJ一次性只给一组数据那while循环也无妨多组数据时反而省心不会因为忘记清空答案而WA。4.2 树状数组版本完整程序树状数组版本我也再给一份比较完整的。离散化的部分我和上面写的一样放在main里。这里有个小优化如果原题明确说了牌面是1到N的排列离散化那一段其实可以省掉因为值域已经天然是N了直接a[i]当下标就行。但写通版总没有坏处遇到值域大的题也能直接套。#include bits/stdc.h using namespace std; const int MAXN 100005; int n; int a[MAXN]; int tree[MAXN]; int lowbit(int x) { return x (-x); } void add(int p, int v) { for (int i p; i n; i lowbit(i)) { tree[i] v; } } int sum(int p) { int res 0; for (int i p; i 0; i - lowbit(i)) { res tree[i]; } return res; } int main() { scanf(%d, n); vectorint sorted; for (int i 1; i n; i) { scanf(%d, a[i]); sorted.push_back(a[i]); } sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int i 1; i n; i) { a[i] lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() 1; } long long ans 0; for (int i n; i 1; --i) { ans sum(a[i] - 1); add(a[i], 1); } printf(%lld\n, ans); return 0; }在main里先离散化再循环是最清晰的结构。如果数据有重复且离散化后排名相同树状数组的count会累积但查询a[i]-1已经把等于自己的排除掉了所以不会把相等元素误算成逆序对。这也是我为什么推荐“从右往左扫”这个写法它天然只统计比当前严格小的元素。4.3 提交时的IO和编译细节这类数据量大的题输入输出优化是必须的。用scanf/printf是一套稳妥方案如果你非要用cin/cout记得在main第一行写上ios::sync_with_stdio(false); cin.tie(nullptr);不然很容易因为IO太慢被卡掉。有人说现在很多OJ的cin加了这两句话也很快但牵涉到竞赛环境我建议还是养成习惯直接用scanf最保险。还有一个细节有些同学在本地用Dev-C或某个旧编译器long long可能在某些平台被写作__int64。现在的在线OJ基本都支持标准C11或更新标准直接写long long就行。如果遇到编译报错优先检查代码里是不是写了变量名冲突比如定义了一个叫left的变量。5. 常见问题与排查实录5.1 答案溢出int装不下逆序对这道题最大的隐藏陷阱就是答案类型。N1e5的时候最大逆序对数接近50亿远超int的约21亿上限。我第一次交就是直接int ans结果小数据全对一上大范围数据就输出负数或莫名其妙的值。排查方法很简单先算一下理论上限。当N1e5N*(N-1)/24,999,950,000这已经超过2^31-1了所以统计变量、加法中间量、输出格式都得换成long long。写归并排序时mid - i 1本身是int但累加到ans时我习惯写(long long)(mid - i 1)以防某些编译器在极端情况下做整型加法时先溢出。养成这个习惯能省去很多查溢出的时间。5.2 离散化下标从1开始不然树状数组直接崩树状数组的add和sum都是从下标1开始操作的。lower_bound返回的下标是0到n-1如果你忘记了加1会出现两个问题一是a[i]0时sum(0)或add(0)会导致死循环或错误二是查询区间整体偏小答案算少。这个问题我在前面已经强调过一次但值得再提因为它真的非常常见。排查方法输出离散化后的数组看看如果有0出现那基本就是忘了加1。或者直接开一个断点看sum(a[i]-1)是不是比预期小。5.3 归并排序统计条件什么时候取等号还是那句话牌面是排列你就随便不会有相等如果题目允许重复数字就必须用。很多同学写归并排序习惯写if (a[i] a[j])这在普通排序里没问题但在求逆序对时遇到相等元素会把本来不构成逆序对的情况也统计进去。记住一句话等于不是逆序所以取左边元素时用保证等于情况下优先把左边元素放进来右边元素等到严格大于左边时再操作。5.4 多组输入没清空状态我前面给的归并版本是每次循环都ans0。如果你写的是全局ans但主函数里没有在每组数据开头重置第二组数据就会把第一组的答案累加进去。树状数组也一样tree数组要在一开始全置零可以用memset(tree, 0, sizeof(tree))。最多见的报错形式就是第一组样例输出正确第二组开始莫名变大。排查这个问题的笨办法是在每组开头输出一个自定义分隔符或者打印一些中间值先确认各组之间互相独立。当然正规做法是养成好习惯先看题目是否说“多组测试数据”不管有没有都写上重置逻辑稳赚不赔。5.5 样例过了却全WA问题多半在读入方式有时候样例实测通过但提交直接WA而且不是RE不是TLE就是错。遇到这种情况我建议大家先检查读入。比如有没有可能牌面数字是0到N-1而不是1到N有没有可能要求排成降序而不是升序这两个问题在变体题里都出现过你不仔细看题默认按升序写自然错一片。读入顺序也是一个点。有的题给两行一行N一行N个牌面数字有的题第一行直接给N和序列在同一行。用cin或scanf按格式读一般问题不大但如果你手动拼接数据或者用了某种自定义快读要格外小心EOF处理。5.6 本地对拍暴力验证模板无论写归并还是树状数组强烈建议养成对拍的习惯。自己写一个暴力函数双层循环统计逆序对然后生成随机小数据把暴力程序的结果和优化程序的结果对比。比如生成一个N100的随机排列用暴力双循环算一次再用归并或树状数组跑一次输出不一致就说明代码有隐蔽bug。对拍听起来麻烦其实能救大命。我印象最深的一次就是树状数组从前往后扫的版本写成了sum(n) - sum(a[i])小数据因为值域小碰巧对一到大值域就翻车。没有对拍工具的话这类边界问题很难定位。5.7 超时了先别急着上优化先看循环里有没有写错如果TLE先确认自己的算法确实是O(N log N)。有些同学写完归并在合并函数里又套了一个循环找逆序对位置复杂度直接变成O(N^2)那就不如不优化。还有一种常见情况是树状数组的add循环写了for (int i p; i n; i i (-i))这里记得用lowbit函数别把i (-i)写反。树状数组虽然简单但lowbit表达式错了最直接的后果是死循环或者更新位置不对。TLE的排查思路先跑一个极限数据看本地运行耗时。1e5的数据O(N log N)应该远小于1秒如果你本地跑了超过两秒说明实现里可能藏了额外的高复杂度操作仔细检查每一个循环。6. 做题方法论从“排牌牌”到一类问题6.1 最小操作次数类问题的三板斧刷题多了你就会发现“排牌牌”不是孤例它代表了一整类“最小操作次数使序列有序”的问题。这类题的通用解法就是先定义一次操作会如何改变某个统计量。相邻交换改变逆序对数量任意交换改变的是置换结构抽出插入改变的是LIS长度。每换一种操作统计量就换一个背后的数据结构和算法也对应换掉。所以以后再看到“最小操作次数”“相邻交换”“任意交换”“调整顺序”这些关键词脑子里应该立刻弹出对应的候选结论。先别急着写代码先把操作翻译成数学模型。这一步通常决定了你能不能AC而不是最后代码写得漂不漂亮。6.2 把模拟操作数学化是第一步我在教朋友时经常说一句话看到排序类操作先想“一步最多能消除多少乱序”。相邻交换一步最多消除一个逆序对这就是下界通过反复交换相邻逆序对又能达到下界这就是最优性证明。同样任意交换一步最多让一个元素归位吗其实不是但它可以每步把一个环的大小减少1所以总代价和环长相关。抽出插入一步可以让一个元素移动到任意位置那不动点越多越好于是LIS就自然浮现。这种“先证下界再构造达到下界的方案”的思考方式是很多算法题的通用钥匙。哪怕不是为了竞赛平时写程序时遇到“最少步骤”的需求也值得先想一想别急着暴力模拟。6.3 刷题经验什么时候能复用很多人刷题是刷一道忘一道看到新题又开始直觉模拟。我的经验是不仅要记住结论还要记住结论的前提。比如逆序对模型成立的前提是“只能交换相邻元素”一旦题目说“可以交换任意相邻的一段”之类的加强操作逆序对结论就可能失效。学会抽象问题、而不是背题才能真正提高。我自己的练习习惯是每AC一道题就在代码旁边写一行注释记录这个题属于哪个模型、用了什么数据结构、时间复杂度多少。日积月累再看到新题模型匹配速度会快很多。这道1618排牌牌就是一个特别典型的“入门逆序对”标记点吃透它的每一步比AC它本身更有价值。最后再分享一个实战里的小技巧。如果你在考试或比赛中一眼认出这是逆序对题但时间紧张不想写归并也不想写树状数组可以赌一下数据范围用分块之类的方法也能过代价是代码更复杂。更稳的做法其实是平时就把归并排序和树状数组两份模板都背得滚瓜烂熟遇到这题直接默写一分钟都不浪费。我后来参加模拟赛时遇到逆序对题基本不犹豫直接在归并排序的else分支里加一行计数这行已经成了肌肉记忆。希望这篇题解能让你也早日形成这种肌肉记忆。