1. 从一道经典题说起逆序对到底在解决什么问题第一次遇到 Ultra-QuickSort 这道题的人大概率会被它的名字骗到。看标题以为是要写一个快排读完题才发现快排只是个幌子真正要算的是逆序对。这个转折其实挺有意思——它恰好说明了一个事实很多排序行为的本质就是在消除逆序对而逆序对的数量就是排序需要付出的“代价”。先把问题说清楚。给定一个长度为 n 的序列如果存在 i j 但 a[i] a[j]那么 (i, j) 就构成一个逆序对。题目要求的就是整个序列里逆序对的总数。序列长度可以到 50 万元素值域在 32 位整数范围内元素还可能重复。这个规模直接决定了暴力 O(n²) 的写法必然超时——50 万的平方是 2500 亿次比较任何语言都扛不住。那这道题适合谁来参考我觉得有三类人值得认真看完。第一类是正在学归并排序或者树状数组想找一个能同时练到这两个知识点的题目第二类是准备算法竞赛或者面试逆序对是一道出现频率极高的模板题第三类是做数据分析或者推荐系统需要衡量两个序列的“混乱程度”或者“一致性”逆序对是一个很自然的度量。不管你是哪一类这篇内容都会把思路、实现、坑点讲透代码可以直接抄。我个人的习惯是遇到这种“看起来简单、规模很大”的题先不急着写代码而是先想清楚三件事数据规模决定了什么复杂度可行、元素值域决定了要不要离散化、重复元素会不会影响计数逻辑。这三件事想明白了后面的实现就是水到渠成。2. 为什么暴力不行复杂度分析与方案选型2.1 暴力枚举的复杂度到底差在哪最直观的做法是双重循环外层 i 从 0 到 n-1内层 j 从 i1 到 n-1只要 a[i] a[j] 就计数加一。这个思路没有任何理解门槛但复杂度是 O(n²)。当 n 500000 时比较次数约为 n(n-1)/2 ≈ 1.25 × 10¹¹ 次。假设每秒能处理 10⁸ 次比较也需要 1250 秒也就是 20 多分钟。这还只是比较没算内存访问的开销。实际跑起来只会更慢。所以暴力的唯一价值就是用来对拍验证。我写任何逆序对代码之前都会先写一个 O(n²) 的暴力版本用来在小数据上验证正确性。这个习惯救过我很多次尤其是树状数组版本下标处理稍微错一点结果就全错没有暴力对拍很难发现。2.2 归并排序顺带就把逆序对算了归并排序求逆序对的核心洞察是在合并两个有序子数组的过程中可以顺便统计跨越两个子数组的逆序对。具体来说当归并到某一步时左半部分 [left, mid] 和右半部分 [mid1, right] 都已经各自有序。我们用两个指针 i 和 j 分别指向两部分的开头。如果 a[i] a[j]说明 a[i] 不大于右边任何一个还没处理的元素不构成逆序对i 后移。如果 a[i] a[j]那么 a[i] 以及左半部分从 i 到 mid 的所有元素都大于 a[j]因为左半部分是有序的。这时候逆序对数量直接加上 mid - i 1然后 j 后移。这个“直接加上 mid - i 1”是整个算法的精髓。它把原本需要逐个比较的操作压缩成了一次加法。每一层归并的时间复杂度是 O(n)总共 log n 层所以整体是 O(n log n)。对于 50 万的数据大约是 50万 × 19 ≈ 950 万次操作秒杀。归并排序的另一个好处是它是稳定排序而且不需要离散化直接处理原始值就行。元素重复也不影响因为判断条件是 a[i] a[j] 时不计数只有严格大于才计数这正好符合逆序对的定义。2.3 树状数组另一种优雅的解法树状数组求逆序对的思路是从右往左扫描统计每个元素右边有多少个比它小的数。具体做法是把元素值离散化到 1 到 m 的排名然后从右往左遍历原序列。对于当前元素 x查询树状数组中排名小于 x 的前缀和这个和就是右边比 x 小的元素个数也就是以 x 为左端点的逆序对数量。查询完之后把 x 的排名位置加一表示这个元素已经出现过。树状数组的查询和更新都是 O(log m)总共 n 次操作所以复杂度是 O(n log m)。m 是不同元素的个数最坏情况下等于 n所以也是 O(n log n)。树状数组的优点是代码相对短而且可以很方便地扩展成“统计每个位置的逆序对数量”这种变体。缺点是需要离散化而且下标从 1 开始写的时候容易在边界上出错。2.4 两种方案的对比与选择对比维度归并排序树状数组时间复杂度O(n log n)O(n log n)空间复杂度O(n) 辅助数组O(m) 树状数组是否需要离散化不需要需要代码长度中等较短边界处理难度较低中等可扩展性一般强稳定性稳定排序不涉及我个人的选择是如果是纯模板题树状数组写起来更快如果需要同时排序或者处理其他逻辑归并排序更自然。这道题两种都能过我下面会把两种实现都写出来你可以根据自己的习惯选。3. 归并排序求逆序对从原理到可运行代码3.1 核心逻辑的逐行拆解归并排序求逆序对的标准写法是在归并函数里加一行计数。我先把关键部分写出来然后逐行解释。long long merge_count(int a[], int temp[], int left, int mid, int right) { int i left, j mid 1, k left; long long cnt 0; while (i mid j right) { if (a[i] a[j]) { temp[k] a[i]; } else { temp[k] a[j]; cnt mid - i 1; } } while (i mid) temp[k] a[i]; while (j right) temp[k] a[j]; for (int p left; p right; p) a[p] temp[p]; return cnt; }这段代码里最关键的是cnt mid - i 1这一行。为什么是 mid - i 1 而不是 1因为当 a[i] a[j] 时由于左半部分 [left, mid] 已经有序所以从 i 到 mid 的所有元素都大于等于 a[i]也就都大于 a[j]。这些元素每一个都和 a[j] 构成一个逆序对所以一次性加上 mid - i 1 个。另一个容易忽略的点是a[i] a[j]里的等号。如果写成a[i] a[j]那么当 a[i] a[j] 时会走 else 分支把相等的元素也当成逆序对结果就错了。逆序对的定义是严格大于所以必须用。3.2 递归框架与全局计数归并排序的主框架是递归的每一层递归返回该层统计到的逆序对数量累加起来就是总数。long long merge_sort(int a[], int temp[], int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt 0; cnt merge_sort(a, temp, left, mid); cnt merge_sort(a, temp, mid 1, right); cnt merge_count(a, temp, left, mid, right); return cnt; }这里用left (right - left) / 2而不是(left right) / 2是为了防止 left right 溢出。虽然对于 50 万的数据int 不会溢出但这是一个好习惯尤其是在处理更大规模或者负数下标的时候。计数变量必须用long long。50 万个元素最坏情况下逆序对数量是 n(n-1)/2 ≈ 1.25 × 10¹¹远超 int 的 21 亿上限。这一点很多人第一次写会踩坑用 int 存结果大数据直接溢出成负数。3.3 完整可运行代码与测试把上面的部分拼起来加上输入输出就是完整的解法。#include cstdio #include cstring const int MAXN 500005; int a[MAXN], temp[MAXN]; long long merge_count(int left, int mid, int right) { int i left, j mid 1, k left; long long cnt 0; while (i mid j right) { if (a[i] a[j]) { temp[k] a[i]; } else { temp[k] a[j]; cnt mid - i 1; } } while (i mid) temp[k] a[i]; while (j right) temp[k] a[j]; for (int p left; p right; p) a[p] temp[p]; return cnt; } long long merge_sort(int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt 0; cnt merge_sort(left, mid); cnt merge_sort(mid 1, right); cnt merge_count(left, mid, right); return cnt; } int main() { int n; while (scanf(%d, n) 1 n ! 0) { for (int i 0; i n; i) scanf(%d, a[i]); printf(%lld\n, merge_sort(0, n - 1)); } return 0; }注意题目是多组输入以 0 结束。这个细节读题时容易漏掉如果只处理一组会 WA。另外数组要开在全局50 万的 int 数组放在栈上可能爆栈全局区更安全。3.4 实操心得三个容易翻车的点第一个坑是等号处理。前面说过了a[i] a[j]必须带等号否则重复元素会被误算成逆序对。我见过不止一个人在这里卡了半天对拍小数据才发现问题。第二个坑是计数变量类型。用 int 存结果n 稍微大一点就溢出。养成习惯只要涉及计数且规模可能到 10⁵ 以上直接用 long long不要省这点内存。第三个坑是递归深度。50 万的数据归并排序的递归深度是 log₂(500000) ≈ 19 层完全没问题。但如果有人写成非递归版本或者用递归处理更大规模要注意栈空间。一般竞赛环境栈是 8MB 或者 1MB19 层递归远远够用。4. 树状数组求逆序对离散化与下标处理4.1 离散化的必要性树状数组的本质是一个支持单点更新和前缀查询的数组它的下标必须是连续的、从 1 开始的整数。但题目给的元素值域是 32 位整数可能是负数可能很大也可能很稀疏。所以必须先把原始值映射到 1 到 m 的排名这个过程叫离散化。离散化的标准做法是把原数组复制一份排序去重然后用二分查找确定每个元素在去重后数组中的位置。这个位置就是它的排名也就是树状数组的下标。int sorted[MAXN], m; for (int i 0; i n; i) sorted[i] a[i]; std::sort(sorted, sorted n); m std::unique(sorted, sorted n) - sorted; for (int i 0; i n; i) { rank[i] std::lower_bound(sorted, sorted m, a[i]) - sorted 1; }这里lower_bound返回的是第一个大于等于 a[i] 的位置减掉起始位置再加 1就是 1-based 的排名。去重是为了让相同元素有相同的排名这样树状数组的每个位置对应一个唯一的值。4.2 从右往左扫描的计数逻辑离散化之后从右往左遍历原数组。对于当前元素它的排名是 r我们查询树状数组中 [1, r-1] 的前缀和这个和就是右边比它小的元素个数。然后把位置 r 加一。long long cnt 0; for (int i n - 1; i 0; i--) { cnt query(rank[i] - 1); update(rank[i], 1); }为什么是查询 r-1 而不是 r因为逆序对要求严格大于排名等于 r 的元素和当前元素相等不构成逆序对。所以只查询严格小于的部分。树状数组的 query 和 update 是标准模板int tree[MAXN]; void update(int pos, int val) { while (pos m) { tree[pos] val; pos pos (-pos); } } int query(int pos) { int sum 0; while (pos 0) { sum tree[pos]; pos - pos (-pos); } return sum; }pos (-pos)是树状数组的核心它取出 pos 的二进制表示中最低位的 1。这个操作决定了树状数组的更新和查询路径也是它 O(log n) 复杂度的来源。4.3 完整代码与边界测试#include cstdio #include algorithm #include cstring const int MAXN 500005; int a[MAXN], sorted[MAXN], rank_arr[MAXN], tree[MAXN]; int n, m; void update(int pos, int val) { while (pos m) { tree[pos] val; pos pos (-pos); } } int query(int pos) { int sum 0; while (pos 0) { sum tree[pos]; pos - pos (-pos); } return sum; } int main() { while (scanf(%d, n) 1 n ! 0) { for (int i 0; i n; i) { scanf(%d, a[i]); sorted[i] a[i]; } std::sort(sorted, sorted n); m std::unique(sorted, sorted n) - sorted; for (int i 0; i n; i) { rank_arr[i] std::lower_bound(sorted, sorted m, a[i]) - sorted 1; } memset(tree, 0, sizeof(int) * (m 1)); long long cnt 0; for (int i n - 1; i 0; i--) { cnt query(rank_arr[i] - 1); update(rank_arr[i], 1); } printf(%lld\n, cnt); } return 0; }测试的时候我一般会用这几组数据输入期望输出说明5 9 1 0 5 46经典样例3 1 2 30已有序3 3 2 13完全逆序4 2 2 2 20全部相等1 50单元素全部相等那组特别重要它验证了等号处理是否正确。如果输出不是 0说明离散化或者查询范围有问题。4.4 树状数组版本的避坑指南第一个坑是离散化后忘记去重。如果不去重相同元素会得到不同的排名树状数组里会出现多个位置对应同一个值查询逻辑就乱了。std::unique必须配合std::sort使用而且它返回的是去重后末尾的迭代器不是新的数组长度要减掉起始位置才是。第二个坑是树状数组清空。多组输入时tree 数组必须清空。但清空整个 MAXN 太慢只需要清空前 m 个位置。用memset(tree, 0, sizeof(int) * (m 1))比循环快也比清空整个数组高效。第三个坑是查询范围。从右往左扫描时查询的是rank_arr[i] - 1不是rank_arr[i]。如果写成后者相等的元素会被算进去结果偏大。这个错误在小数据上可能看不出来但大数据上会明显偏差。5. 常见问题与排查技巧实录5.1 结果溢出成负数怎么办这是最典型的问题。逆序对数量在 n 500000 时可以达到约 1.25 × 10¹¹而 int 的上限是 2147483647约 2.1 × 10⁹。两者差了两个数量级。如果你发现小数据结果正确大数据结果是负数或者明显偏小第一反应就是检查计数变量是不是 int。解决方法很简单把计数变量、函数返回值、输出格式全部改成 long long。C 里printf用%lldscanf读 int 用%d读 long long 用%lld。不要混用否则会读错。5.2 多组输入的初始化问题这道题是多组输入以 0 结束。很多人第一组结果正确第二组就错了原因就是全局数组没有清空。归并排序版本里temp 数组每次都会被覆盖所以不需要清空但树状数组版本里tree 数组必须清空。我的习惯是在每组数据的开头把所有需要重置的全局变量重新初始化一遍。不要依赖全局变量的默认零值因为上一组数据可能已经把它改了。5.3 离散化后排名从 0 开始还是从 1 开始树状数组的下标必须从 1 开始因为pos (-pos)在 pos 0 时是 0会导致死循环。所以离散化后的排名必须加 1。lower_bound返回的是 0-based 的偏移量加 1 之后就是 1-based 的排名。如果你不小心用了 0-based 排名update 和 query 都会出问题。update 在 pos 0 时直接死循环query 在 pos 0 时返回 0但逻辑上应该是查询空集。所以这个加 1 不能省。5.4 归并排序的递归边界归并排序的递归终止条件是left right不是left right。当 left right 时只有一个元素本身就是有序的不需要合并直接返回 0。如果写成left right那么单元素区间会继续递归导致无限递归或者数组越界。这个错误在调试时表现为栈溢出或者段错误不容易直接定位到递归条件。我的建议是写递归函数时先把终止条件写对再写递归体。5.5 常见问题速查表现象可能原因排查方法小数据对大数据负数计数变量用了 int检查所有计数相关变量类型第二组数据开始出错全局数组未清空每组数据前重置 tree 等数组结果偏大等号处理错误检查a[i] a[j]是否带等号结果偏小查询范围错误检查树状数组查询是否用了 r-1程序崩溃递归边界错误检查left right离散化后结果全错排名未加 1检查 lower_bound 结果是否 1多组输入死循环终止条件未处理检查n ! 0是否生效5.6 对拍最可靠的验证手段不管你写的是归并还是树状数组我都强烈建议写一个暴力版本用来对拍。暴力版本虽然慢但逻辑简单不容易错。随机生成小规模数据比如 n 在 1 到 100 之间元素值在 1 到 20 之间跑几百组对比两个版本的结果。如果全部一致基本可以确定正确性。对拍脚本可以用 Python 写也可以用 shell。核心就是生成随机输入、跑两个程序、比较输出。这个过程花不了多少时间但能帮你排除掉 90% 以上的逻辑错误。6. 从这道题延伸出去逆序对的真实应用场景6.1 衡量序列的混乱程度逆序对最直接的应用就是衡量一个序列的有序程度。逆序对为 0 表示完全有序逆序对达到最大值 n(n-1)/2 表示完全逆序。在推荐系统里可以用逆序对来衡量推荐列表和用户真实偏好列表之间的差异。差异越小说明推荐越符合用户口味。这个思路在信息检索里也有对应叫 Kendall tau 距离。它本质上就是逆序对数量归一化之后的结果。两个排名列表的 Kendall tau 距离越小说明它们越一致。6.2 排序算法的下界分析逆序对的数量还决定了基于比较的排序算法需要多少次交换。冒泡排序每次交换恰好消除一个逆序对所以冒泡排序的交换次数等于逆序对数量。插入排序的移动次数也等于逆序对数量。这个性质在分析算法行为时很有用。更进一步任何基于比较的排序算法在最坏情况下至少需要 log₂(n!) 次比较而 log₂(n!) ≈ n log n - n这和逆序对数量的对数是一个量级。所以逆序对不仅是排序的“代价”也是排序复杂度的下界来源。6.3 数据一致性检测在分布式系统或者数据同步场景里逆序对可以用来检测两个数据副本之间的差异。如果两个副本的元素集合相同但顺序不同逆序对数量可以量化它们的差异程度。差异越大说明同步越不完整需要优先处理。这个思路在版本控制、日志比对、基因序列分析里都有应用。比如基因序列的倒位检测本质上就是找逆序对集中的区域。6.4 竞赛中的变体题型逆序对在竞赛里有很多变体。比如“每个位置的逆序对数量”、“区间逆序对查询”、“动态逆序对”、“三维偏序”等等。这些变体大多需要结合其他数据结构比如线段树、CDQ 分治、莫队算法。但万变不离其宗核心还是逆序对的计数逻辑。如果你能把这道题吃透后面遇到“统计左边比它大的数”或者“统计右边比它小的数”这类问题都能很快找到思路。因为逆序对本质上就是“左边大于右边”的计数换个方向就是“右边小于左边”逻辑是相通的。7. 我个人的一些实操体会写逆序对这道题我最大的体会是不要急着写代码先把计数逻辑想清楚。归并排序的计数发生在合并阶段树状数组的计数发生在查询阶段两者的时机不同但本质都是在统计“左边大于右边”的组合。想清楚这个本质代码只是表达方式。另一个体会是类型和边界比算法本身更容易出错。算法思路大家都能理解但 long long、等号、下标从 1 开始、多组输入清空这些细节才是真正拉开差距的地方。我见过太多人思路完全正确但因为一个 int 溢出或者一个等号写错调了半天。最后分享一个小技巧如果你不确定自己的代码是否正确先跑小数据再跑大数据。小数据验证逻辑大数据验证性能和溢出。两者都过了基本就稳了。如果只能选一个我选小数据对拍因为它能发现绝大多数逻辑错误。这道题后续还可以这样扩展把静态逆序对改成动态的每次修改一个元素后查询逆序对总数这就需要用树套树或者分块。或者把一维逆序对扩展到二维变成三维偏序问题那就需要 CDQ 分治。但不管怎么扩展基础版本的逆序对计数逻辑都是绕不开的第一步。