逆序对是数组中满足iarr[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范围
示例片段（核心逻辑）：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
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 <h3>递归结构和边界容易错在哪</h3>
<p>常见错误集中在递归划分和合并范围不一致：</p>
<ul>
<li>
<code>mergeSort</code> 递归调用时，右半区间应为 <code>[m+1, r]</code>，不是 <code>[m, r]</code>，否则重叠或漏元素</li>
<li>
<code>merge</code> 中计算 <code>mid - i + 1</code> 时，<code>mid</code> 必须是当前左半区间的右端点（即 <code>m</code>），不是原始数组的中点</li>
<li>递归终止条件是 <code>l >= r</code>，不是 <code>l == r</code>，避免单元素时跳过</li>
<li>传入 <code>merge</code> 的 <code>r</code> 是闭区间端点，别写成开区间导致越界</li>
</ul>
<h3>完整可跑的最小实现长什么样</h3>
<p>去掉冗余封装，只保留核心逻辑：</p>
<pre class="brush:php;toolbar:false;">
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 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>// 调用方式：
// vector<int> a = {2, 3, 8, 6, 1};
// long long ans = merge_sort(a, 0, a.size()-1);</int></p></int></int></int>
注意：原数组会被排序，如需保留原顺序，先拷贝一份再传入。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
