高效计算逆序对：归并排序分治法详解与Python实现

这是一个经典的**求逆序对个数**问题。逆序对定义为：满足 $ i < j $ 且 $ a_i > a_j $ 的下标对 $ (i, j) $ 的数量。 --- ### ✅ 解法分析 #### ❌ 暴力解法（O(n²)） 遍历所有 $ i < j $，统计 $ a_i > a_j $ 的个数。 适用于小规模数据（如 $ n \leq 10^4 $），但本题中 $ n $ 可能较大（虽然未明确上限，但通常此类题 $ n \leq 5 \times 10^5 $），暴力会超时。 #### ✅ 最优解法：归并排序（分治）—— O(n log n) 在归并排序的 `merge` 过程中，当从右半部分取元素 `a[j]` 时，说明左半部分中**所有尚未合并的元素**都大于 `a[j]`（因为左右两半已各自有序），这些元素个数即为当前 `a[j]` 能构成的逆序对数。 > 🔑 关键点：**仅当 `a[i] > a[j]` 时，在左半段剩余未处理的元素个数（`mid - i + 1`）全部与 `a[j]` 构成逆序对。** ⚠️ 注意：题目说“序列中可能有重复数字”，而逆序对定义是 **严格大于**（$ a_i > a_j $），所以相等不算逆序对。因此归并时，当 `a[i] == a[j]`，应优先取左段（不触发逆序计数），或取右段但**不计数** —— 我们采用标准写法：**只有 `a[i] > a[j]` 才计数**。 --- ### ✅ Python 实现（归并排序计数） ```python def merge_sort_count(arr): if len(arr) <= 1: return 0 mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] count = merge_sort_count(left) + merge_sort_count(right) # 归并过程 & 计数 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 count += len(left) - i # 左边剩余所有元素都 > right[j] k += 1 # 复制剩余 while i < len(left): arr[k] = left[i] i += 1 k += 1 while j < len(right): arr[k] = right[j] j += 1 k += 1 return count # 主程序 n = int(input()) a = list(map(int, input().split())) # 使用副本，避免修改原数组（可选） arr = a[:] ans = merge_sort_count(arr) print(ans) ``` --- ### ✅ 样例验证 输入：`[5, 4, 2, 6, 3, 1]` 手动列出所有逆序对（i < j, a[i] > a[j]）： - 5: >4,2,3,1 → 4 个 - 4: >2,3,1 → 3 个 - 2: >1 → 1 个 - 6: >3,1 → 2 个 - 3: >1 → 1 个 总计：4+3+1+2+1 = **11** ✅ --- ### 🧠 进阶说明（可选） - 若需离散化（应对大数值但稀疏的情况，如 $ a_i \leq 10^9 $ 但 $ n \leq 5\times10^5 $），可用坐标压缩（排序去重后映射），再用树状数组 / 线段树求解（也是 O(n log n)）。 - 本题直接归并即可，无需离散化（Python 中 `int` 足够，且归并不依赖值域）。 --- ### 💡 开发建议 - 写归并时注意索引边界，尤其 `len(left) - i` 是关键计数式； - 测试用例务必包含：空数组、单元素、升序、降序、含重复（如 `[2,2,1]` → 逆序对为 `(0,2)` 和 `(1,2)` 共 **2** 个）； - Python 中递归深度限制：若 `n` 极大（如 >10⁵），可设 `sys.setrecursionlimit(300000)`，但更推荐非递归归并（或用迭代版）；不过本题一般不会卡递归。 --- ######[AI写代码神器 | 1144点数解答 | 2026-03-18 17:49:11]