归并排序边合并边统计逆序对是高效解法：在merge过程中，当右半段元素a[j]被取出时，左半段剩余元素个数(m−i+1)即为新增逆序对数；需用long long防溢出，相等时取左段元素以避免误计，空间复杂度o(n)。

用归并排序边合并边统计逆序对数量

直接暴力两重循环检查每对 (i, j)（i 且 <code>a[i] > a[j]）时间复杂度是 O(n²)，数组稍大（比如 n > 10⁵）就会超时。真正实用的做法是在归并排序的 merge 过程中累计逆序数：当把右半段的元素 a[j] 取出放入临时数组时，说明左半段从当前指针 i 开始到末尾的所有元素都大于 a[j]，这些都构成逆序对。

关键点在于：左半段和右半段各自有序，所以一旦 a[i] > a[j]，那么 a[i], a[i+1], ..., a[mid] 全都 > a[j]。

示例核心逻辑片段：

long long merge_count(vector<int>& a, 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>逆序对总数最多可达 <code>n*(n-1)/2</code>，当 <code>n = 10⁵</code> 时，结果接近 <code>5×10⁹</code>，已超出 <code>int</code> 范围（约 <code>2.1×10⁹</code>）。必须用 <code>long long</code> 存储计数变量和返回值，否则中间累加会静默溢出，结果错误。</p>
<ul>
<li>所有递归返回值类型、合并函数返回类型、顶层调用的接收变量，都得是 <code>long long</code>
</li>
<li>别用 <code>int</code> 做计数器，哪怕你本地测试小数据没问题，上线就崩</li>
<li>如果题目明确要求模某个数（如 <code>10⁹+7</code>），才在每次 <code>+=</code> 后取模；否则不要提前取模，会干扰实际计数值</li>
</ul>
<h3>原地修改 vs 额外空间权衡</h3>
<p>标准归并求逆序对需要辅助数组做 <code>merge</code>，空间复杂度 <code>O(n)</code>。C++ 中不能像 Python 那样轻松切片，所以通常用 <code>vector<int></int></code> 传引用 + 辅助数组实现。没有靠谱的 <code>O(1)</code> 空间解法——试图用插入排序或树状数组虽然可行，但前者仍是 <code>O(n²)</code>，后者需额外编码且常数大。</p>
<p>如果你被卡内存（极少见），可考虑用 <code>std::inplace_merge</code>，但它不暴露合并过程，无法插入手动计数逻辑；所以务实做法就是接受 <code>O(n)</code> 额外空间，写清楚 <code>merge</code> 步骤。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
														src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
													<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<ul>
<li>别为了省几 MB 内存去魔改归并逻辑，容易引入边界错误</li>
<li>辅助数组大小严格为 <code>r - l + 1</code>，不是整个原数组长度</li>
<li>拷回原数组时下标要对齐，错一位会导致后续递归全乱</li>
</ul>
<h3>处理重复元素时的相等判断要小心</h3>
<p>逆序对定义是 <code>i  且 <code>a[i] > a[j]</code>，**不包含等于**。所以在 <code>merge</code> 中，只有 <code>a[i] > a[j]</code> 才触发计数；<code>a[i] == a[j]</code> 时应归入“不构成逆序”，让左段元素先出（即条件写成 <code>a[i] ），否则会多算或少算。</code></code></p>
<p>错误写法：<code>if (a[i]  → 当相等时把右段先取，导致左段剩余元素被误计入逆序</code></p>
<p>正确写法：<code>if (a[i]  → 相等时取左段，不触发计数，逻辑干净</code></p>
<p>这个细节在含大量重复值的测试用例（如全相同数组）里会直接暴露问题。</p>
<p>最易被忽略的是：递归分治的边界条件（<code>l >= r</code> 时返回 0）和 <code>merge</code> 中 <code>i</code>、<code>j</code> 的初始位置是否对应当前子区间——错一个下标，整个计数就偏移。建议先拿长度为 2 和 4 的手工数组单步验证 <code>merge_count</code> 函数输出是否匹配手算结果。</p></int></int>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！