题目原型为洛谷 P1908 逆序对。本题的考点是在归并排序的合并阶段统计逆序对：排序的中间过程本身携带统计信息，不必排完再回头数。

目标

完成本题后，你应该能够：

• 解释归并排序「合并两个有序子数组」时如何一次性算出多组逆序对；
• 把逆序对计数从暴力 O(n²) 降到 O(n log n)；
• 说明为什么答案需要用 long long。

前置知识

• 11.1 归并排序的递归与合并过程；
• 逆序对的定义：若 i < j 且 a[i] > a[j]，则 (i, j) 是一对逆序对。

题目

给一个长度为 n 的整数序列 a，求其中逆序对的个数。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示序列 a。

输出格式

一行一个整数，表示逆序对的总数。

数据范围

项目	范围
序列长度 n	1 ≤ n ≤ 5 × 10⁵
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

6
5 4 2 6 3 1

样例输出

11

样例解释

序列 5 4 2 6 3 1 共有 11 对逆序对：(5,4)(5,2)(5,3)(5,1)(4,2)(4,3)(4,1)(2,1)(6,3)(6,1)(3,1)。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-11/exercise/E-11-02-inversion-pairs
pnpm lab:score -- labs/chapter-11/exercise/E-11-02-inversion-pairs

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序（0 个）、降序（最多）、含重复值三种情况都通过
• 能说出「mid - i + 1」为什么等于新增逆序对的个数

思考题

1. 为什么答案最多约 n(n-1)/2，n = 5×10⁵ 时会超出 int 的范围？
2. 快排的划分阶段能不能像归并这样统计逆序对？为什么归并更适合？

题解

点击查看题解

思路

归并排序合并两个有序子数组 [l, mid] 和 [mid+1, r] 时：

• 左指针 i、右指针 j 分别从两段头部开始；
• 若 a[j] < a[i]，则右半的 a[j] 比左半从 i 到 mid 的所有元素都小，一次就构成 mid - i + 1 组逆序对，累加即可。

这利用了「两段内部各自有序」的性质，把一次跨越比较扩成一批逆序对。

复杂度分析

• 时间复杂度：O(n log n)；
• 空间复杂度：O(n)（归并辅助数组）。