从归并排序到逆序对：一个算法竞赛选手必须掌握的‘降维打击’技巧

从归并排序到逆序对：算法竞赛中的降维打击艺术

在算法竞赛的战场上，逆序对问题就像一座看似坚不可摧的堡垒——表面上看，它只需要简单的双重循环就能解决，但当数据规模扩大到十万级别时，O(n²)的暴力解法立刻暴露出致命缺陷。这时，归并排序这个看似普通的排序算法，却能化身为一柄精准的手术刀，以O(n log n)的时间复杂度优雅地解决问题。这种将基础算法"玩出花"的能力，正是区分普通选手与顶尖选手的关键所在。

1. 逆序对问题的本质与挑战

逆序对，简单来说就是在一个序列中，如果前面的数比后面的数大，那么这两个数就构成一个逆序对。例如在序列[3,1,2]中，(3,1)和(3,2)都是逆序对。这个问题看似简单，但在大规模数据下却暗藏杀机。

1.1 暴力解法的局限性

最直观的解法当然是双重循环：

def count_inversions_naive(arr): count = 0 n = len(arr) for i in range(n): for j in range(i+1, n): if arr[i] > arr[j]: count += 1 return count

这种解法在小数据量时工作良好，但当n=5×10⁵时，操作次数将达到： (5×10⁵ × (5×10⁵ - 1))/2 ≈ 1.25×10¹¹次

即使现代CPU每秒能执行10⁹次操作，这样的算法也需要125秒才能完成——远超竞赛题目通常设置的1秒时间限制。

1.2 数据规模的陷阱

在NOI、洛谷等平台的题目中，逆序对问题通常会设置以下数据规模：

这里隐藏着两个常见坑点：

1. 时间复杂度陷阱：没有意识到O(n²)解法不可行
2. 数据溢出陷阱：使用int类型存储结果导致溢出

2. 归并排序的隐藏能力

归并排序之所以能高效统计逆序对，关键在于它分治过程中的合并操作——这正是统计逆序对的黄金时机。

2.1 归并排序的基本框架

先看标准的归并排序实现：

void mergeSort(int l, int r) { if(l >= r) return; int mid = (l+r)/2; mergeSort(l, mid); mergeSort(mid+1, r); merge(l, mid, r); // 合并两个有序子数组 }

这个分治过程本身已经将问题分解为更小的子问题，而逆序对可以分为三类：

1. 左半部分的逆序对
2. 右半部分的逆序对
3. 横跨左右两部分的逆序对

前两类在递归调用中已经解决，关键在于第三类。

2.2 合并时的逆序对统计

在合并两个有序子数组时，我们可以顺便统计跨区间的逆序对。具体逻辑是：

当需要将右子数组的元素a[j]放入合并数组时，左子数组中所有尚未被合并的元素都比a[j]大，因此它们都与a[j]构成逆序对。

while(i <= mid && j <= r) { if(a[i] <= a[j]) { t[k++] = a[i++]; } else { t[k++] = a[j++]; cnt += mid - i + 1; // 关键统计语句 } }

注意：必须使用<=而非<来保证排序的稳定性，即相等元素的原始顺序不被改变。

3. 算法实现与细节处理

3.1 完整代码实现

以下是经过竞赛验证的C++实现：

#include <bits/stdc++.h> using namespace std; #define N 500005 // 根据题目调整大小 int n, a[N], t[N]; long long cnt; // 必须使用long long void mergeSort(int l, int r) { if(l >= r) return; int mid = (l+r)/2; 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]) { t[k++] = a[i++]; } else { t[k++] = a[j++]; cnt += mid - i + 1; } } while(i <= mid) t[k++] = a[i++]; while(j <= r) t[k++] = a[j++]; for(int i = l; i <= r; ++i) a[i] = t[i]; } int main() { cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; mergeSort(1, n); cout << cnt; return 0; }

3.2 关键细节解析

1. 数组大小设置：

   • 对于ybt/OpenJudge题目，N=100005足够
   • 对于洛谷P1908，必须设为N=500005

2. 变量类型选择：

   • cnt必须为long long，int会导致溢出
   • 当n=5×10⁵时，最大逆序对数约为1.25×10¹¹，远超int的2.1×10⁹上限

3. 边界条件处理：

   • 递归终止条件if(l >= r)不能写成if(l == r)
   • 合并时的比较必须使用<=保证稳定性

4. 技巧扩展与实战应用

掌握了这个技巧后，我们可以将其应用于各种变种问题，实现真正的"降维打击"。

4.1 相关问题变种

1. 求每个元素的逆序数：在合并时记录每个元素参与构成的逆序对数
2. 二维逆序对：先对一维排序，转化为一维问题
3. 带权逆序对：在统计时乘以相应的权重

4.2 竞赛中的识别技巧

当遇到以下特征时，考虑使用归并排序解逆序对问题：

• 题目明显与元素相对顺序有关
• 数据规模在10⁵级别
• 暴力解法时间复杂度为O(n²)的问题

4.3 性能对比

下表展示了不同方法在随机数据下的表现：

在实际竞赛中，这种性能差异直接决定了能否通过所有测试用例。

5. 思维训练与进阶之路

理解归并排序求逆序对的本质后，可以将其视为一种分治统计的范式。这种思维可以迁移到许多其他问题：

1. 统计区间满足某种性质的元素对：只要性质在合并时能够高效计算
2. CDQ分治：处理高维偏序问题的利器
3. 树状数组解法：另一种O(n log n)解法，适合动态统计

我曾在一个区域赛题目中遇到需要统计"三元逆序对"的问题，正是基于对归并排序的深刻理解，才能快速将其转化为多个一维逆序对问题的组合。这种将复杂问题拆解为已知模式的能力，才是算法竞赛的真正精髓。