逆序对是数组中满足i<j且arr[i]>arr[j]的下标对；暴力法O(n²)易超时，分治法在归并排序合并时，当left[i]>right[j]则累加mid-i+1个逆序对，需用long long防溢出。
什么是逆序对，为什么不能暴力数
逆序对是指数组中满足 i 且 <code>arr[i] > arr[j] 的下标对。暴力法两层循环时间复杂度是 O(n²)，10⁵ 规模数组就超时。分治的核心思路是：在归并排序过程中，每次合并左右两个已排序子数组时，一旦发现 left[i] > right[j]，说明 left[i..mid] 全部大于 right[j]，能一次性累加 mid - i + 1 个逆序对。
归并过程中怎么统计逆序对数量
关键在 merge 函数里——不是只做归并，还要在右半边元素被取出来时，计算它“跨过”了多少左半边剩余元素：
- 当
left[i] ：正常取 <code>left[i]，不产生新逆序对 - 当
left[i] > right[j]：此时right[j]比从i开始的所有左半边剩余元素都小，逆序对数 +=mid - i + 1 - 必须用
long long累加，因为最多有n*(n-1)/2对（如降序数组），n=1e5时超int范围
示例片段（核心逻辑）：
long long merge(vector<int>& arr, int l, int m, int r) {
vector<int> tmp(r - l + 1);
int i = l, j = m + 1, k = 0;
long long inv = 0;
while (i <= m && j <= r) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
inv += m - i + 1; // 关键：左半边剩余元素全部构成逆序
}
}
// ... 剩余部分复制
copy(tmp.begin(), tmp.end(), arr.begin() + l);
return inv;
}
递归结构和边界容易错在哪
常见错误集中在递归划分和合并范围不一致：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
-
mergeSort递归调用时，右半区间应为[m+1, r]，不是[m, r]，否则重叠或漏元素 -
merge中计算mid - i + 1时，mid必须是当前左半区间的右端点（即m），不是原始数组的中点 - 递归终止条件是
l >= r，不是l == r，避免单元素时跳过 - 传入
merge的r是闭区间端点，别写成开区间导致越界
完整可跑的最小实现长什么样
去掉冗余封装，只保留核心逻辑：
long long merge_count(vector<int>& arr, int l, int m, int r) {
vector<int> tmp(r - l + 1);
int i = l, j = m + 1, k = 0;
long long res = 0;
while (i <= m && j <= r) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else {
tmp[k++] = arr[j++];
res += m - i + 1;
}
}
while (i <= m) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
for (i = l, k = 0; i <= r; i++, k++) arr[i] = tmp[k];
return res;
}
<p>long long merge_sort(vector<int>& arr, int l, int r) {
if (l >= r) return 0;
int m = l + (r - l) / 2;
return merge_sort(arr, l, m) +
merge_sort(arr, m + 1, r) +
merge_count(arr, l, m, r);
}</p><p>// 调用方式：
// vector<int> a = {2, 3, 8, 6, 1};
// long long ans = merge_sort(a, 0, a.size()-1);</p>注意：原数组会被排序，如需保留原顺序，先拷贝一份再传入。
