逆序对是数组中满足 i arr[j] 的索引对；暴力双重循环时间复杂度 o(n²)，n > 10⁵ 时超时，应改用归并排序分治法，在合并时当 arr[i] > arr[j] 批量累加 mid - i + 1。
什么是逆序对，为什么不能用暴力双重循环
逆序对是指数组中满足 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++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 递归终止条件是
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 <h3>容易被忽略的边界和调试技巧</h3>
<p>小数组（如长度 2 或 3）手动验证逻辑是否成立，比看大数组输出更有效；归并过程中的 <code>cnt</code> 累加位置错一位、<code>mid</code> 计算写成 <code>(l + r) / 2</code>（整型溢出）都是高频翻车点。</p>
<ul>
<li>用 <code>int mid = l + (r - l) / 2</code> 替代 <code>(l + r) / 2</code>，防 <code>l+r</code> 溢出</li>
<li>测试用例至少覆盖：空数组、单元素、已排序、完全逆序、含重复元素（如 <code>[2,2,1]</code> —— 逆序对是 2 个，不是 1 个）</li>
<li>如果返回值始终为 0，优先检查是否在 <code>merge_count</code> 外忘了累加左右子问题的返回值</li>
</ul>
<p>归并统计逆序对本质是“修改版归并排序”，所有改动都集中在合并阶段的计数逻辑，其余部分和标准归并一致——别试图在快排或堆排里硬套，那只会绕远。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
