<p>逆序对是数组中满足 i < j 且 arr[i] > arr[j] 的索引对；暴力双重循环时间复杂度 O(n²)，n > 10⁵ 时超时，应改用归并排序分治法，在合并时当 arr[i] > arr[j] 批量累加 mid - i + 1。</p>
什么是逆序对，为什么不能用暴力双重循环
逆序对是指数组中满足 i 且 <code>arr[i] > arr[j] 的索引对 (i, j)。暴力法写两层 for 循环确实能统计，但时间复杂度是 O(n²)，当 n 超过 10⁵ 就会超时——这不是理论风险，是实际跑不下去。
真正可行的解法是基于归并排序的分治：在每次合并两个有序子数组时，一旦发现左半边的某个元素大于右半边的当前元素，说明左半边从该位置到末尾的所有元素都大于它，可以批量计数。
归并过程中如何正确累加逆序对数量
关键不是“发现 arr[i] > arr[j] 就加 1”，而是加 mid - i + 1（假设左右子数组范围是 [l, mid] 和 [mid+1, r]，当前左指针为 i，右指针为 j）。
- 因为
left[i] > right[j]，而left[i..mid]是升序的，所以left[i], left[i+1], ..., left[mid]全部 >right[j] - 必须在把
right[j]放入临时数组前就累加，否则会漏掉或重复 - 只在
left[i] > right[j]分支里加，时不加——逆序对定义严格要求“大于”
C++ 实现要点：递归边界、临时数组、long long 防溢出
逆序对总数可能达到 n*(n-1)/2，比如完全逆序的 10⁵ 元素数组，结果约 5×10⁹，int 存不下，必须用 long long。
立即学习“C++免费学习笔记（深入）”；
- 递归终止条件是
l >= r，不是l == r（避免单元素数组误进递归） - 临时数组不要在每次递归里
new或vector构造，应复用一个全局/传入的vector<int>& tmp</int>，否则频繁分配拖慢性能 - 合并时拷贝回原数组要用
std::copy或循环，别用assign，避免越界
示例核心片段：
long long merge_count(vector<int>& arr, vector<int>& tmp, int l, int mid, int r) {
long long cnt = 0;
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
cnt += mid - i + 1; // 关键：批量计数
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
copy(tmp.begin() + l, tmp.begin() + r + 1, arr.begin() + l);
return cnt;
}容易被忽略的边界和调试技巧
小数组（如长度 2 或 3）手动验证逻辑是否成立，比看大数组输出更有效；归并过程中的 cnt 累加位置错一位、mid 计算写成 (l + r) / 2（整型溢出）都是高频翻车点。
- 用
int mid = l + (r - l) / 2替代(l + r) / 2，防l+r溢出 - 测试用例至少覆盖：空数组、单元素、已排序、完全逆序、含重复元素（如
[2,2,1]—— 逆序对是 2 个，不是 1 个） - 如果返回值始终为 0，优先检查是否在
merge_count外忘了累加左右子问题的返回值
归并统计逆序对本质是“修改版归并排序”，所有改动都集中在合并阶段的计数逻辑，其余部分和标准归并一致——别试图在快排或堆排里硬套，那只会绕远。
