归并排序中统计逆序对的关键是在合并阶段：当右子数组元素a[j]小于左子数组元素a[i]时，因左子数组有序，a[i]至a[mid]均大于a[j]，故新增逆序对数量为mid−i+1，并累加至总答案。
归并排序中如何顺便统计逆序对
归并排序天然适合统计逆序对，因为合并过程中，当 right[j] 小于 left[i] 时，说明 left[i] 及其右边所有元素都与 right[j] 构成逆序对。这个数量就是 mid - i + 1（假设 left 是左半段，索引从 l 到 mid）。
关键不是“额外加个计数器”，而是把计数逻辑嵌入到 merge 的比较分支里——只在 right[j] 成立时累加，且加的是剩余未处理的左段元素个数。
- 必须用 long long 存逆序对总数，
int容易溢出（比如 1e5 个元素全逆序，结果约 5e9） - 递归分治部分和普通归并排序完全一致，不改动
mergeSort()结构 - 不能在
left[i] 分支里计数，那是正序关系
手写 merge 时容易漏掉的边界和拷贝细节
很多实现崩溃或结果错误，不是算法逻辑错，而是数组索引越界或临时空间没填满。标准做法是：申请一个和当前区间等长的临时数组 temp，merge 时把左右两段有序序列归并进 temp，最后再 memcpy 回原数组。
注意三个下标变量的初始值：i = l, j = mid + 1, k = 0（temp 起始索引）。循环条件必须是 i ，而不是 <code>i 这类常见笔误。
- 合并完后，别忘了把剩余的左段（
i ）或右段（<code>j ）全部复制进 <code>temp - 最后用
std::copy(temp.begin(), temp.end(), arr.begin() + l)或memcpy写回，不能只拷一部分 - 如果用 vector 传参，确保每次递归操作的是原数组的引用，避免意外拷贝
用 std::inplace_merge 能否简化实现？
不能直接用于统计逆序对。虽然 std::inplace_merge 可以就地归并两个相邻有序段，但它不暴露内部比较过程，无法插入计数逻辑。你只能自己实现 merge 步骤。
有人试图在调用 std::inplace_merge 前手动计算跨段逆序对数量，但这是错的：它内部可能用不同策略（如缓冲区+旋转），不保证按传统二路归并顺序执行比较，因此无法可靠推导逆序对来源。
- 依赖
std::inplace_merge会导致结果不可预测，尤其数据量大或编译器优化级别高时 - 即使加上
std::stable_sort，也无法获取中间状态的逆序信息 - 老老实实写自己的
merge函数，控制权在自己手里
测试时怎么验证逆序对数量算对了？
小规模数据（比如长度 ≤ 20）可以直接暴力双重循环验证：for (i = 0; i a[j]) cnt++。这是黄金标准，但只适用于 O(n²) 可接受的场景。
对于大数组，重点检查几个典型 case：
- 升序数组 → 逆序对为 0
- 降序数组 → 逆序对为
n*(n-1)/2 - 单个元素、空数组 → 返回 0
- 含重复元素时，定义要明确：通常
a[i] > a[j]（i == 不算
最容易被忽略的是：归并过程中，left[i] == right[j] 时，必须把 left[i] 先拷贝（即稳定归并），否则会漏计或重复计——这直接影响逆序对定义是否满足稳定性要求。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
