上一章你手写了归并排序，重点是那个「合并」。
这一章的题目 —— 求逆序对 —— 表面上和排序毫无关系。 但它的正解，就是在合并那一步里加一句计数，其他一个字都不改。
这种「旧零件解新问题」的体验，是算法学习里最爽的时刻之一。 更重要的是，它会让你养成一个习惯： 看到一道新题，先想想手上已有的零件能不能改一改就用上。
1 一句话问题
给一个数组，求有多少对下标 (i, j) 满足 i < j 且 a[i] > a[j]。
这样的一对叫做一个逆序对 —— 排在前面、但数值更大。
输入 6
3 1 4 1 5 2
输出 6
数一数：(3,1) (3,1) (3,2) (4,1) (4,2) (5,2)
注意有两个 1，所以 3 和两个 1 各算一对它衡量「这个序列有多乱」。
- 完全升序 → 0 对（最整齐）
- 完全降序 →
n(n-1)/2对（最乱，任意两个都是逆序）
还有个很实用的含义：逆序对的个数 = 用冒泡排序把它排好所需的交换次数。 因为冒泡每次只交换相邻两个，而交换一次相邻的逆序对，逆序对总数正好减一。
（想想为什么：交换相邻两个元素，只会改变它们这一对的相对顺序， 其他所有对的相对顺序都没变。）
2 暴力：每一对都看一遍
点「运行 ▶」看结果
O(n²)。思路无可挑剔，就是慢。
n = 10⁵ 时最多有 n(n-1)/2 ≈ 50 亿对 —— int 装不下（上限约 21 亿）。
更阴险的是：用小数据对拍根本查不出这个错误。
小数据的答案才几十，int 完全够用，对拍会全过，然后你在正式提交时得到 0 分。
对拍查不出溢出。 这是它的第二个盲区（第一个是「两份程序错得一模一样」，见第 9 章）。
3 实测：它有多慢
本机实测（1..n 的随机排列）：
| n | 暴力 O(n²) | 归并 O(n log n) | 逆序对个数 |
|---|---|---|---|
| 20 000 | 0.42 秒 | 0.004 秒 | 约 1.0 亿 |
| 30 000 | 0.96 秒 | 0.005 秒 | 约 2.2 亿 |
| 50 000 | 2.67 秒 | 0.007 秒 | 约 6.2 亿 |
注意最右边那一列：n = 50000 时答案已经是 6.2 亿了。
n = 100000 时是 25 亿 —— 正好越过 int 的边界。
4 ★ 关键的一步
分治三步：分 → 治 → 合。
逆序对总数 = 左半边内部的 + 右半边内部的 + 一左一右的
↑递归解决 ↑递归解决 ↑这是唯一要动脑的部分前两项交给递归（第 1 章：信任那个还没写完的函数）。 关键是第三项：一个下标在左半边、一个在右半边的逆序对，怎么数？
如果两个半边都已经排好序了（而这正是归并排序帮我们做到的）， 那么合并的时候：
左半边: [ 2 5 8 ] 右半边: [ 1 6 ]
↑i ↑j
当前要比较 2 和 1。2 > 1，所以取右边的 1。
但请注意 —— 左半边是有序的，2 后面的 5 和 8 也一定比 1 大！
于是 (2,1)、(5,1)、(8,1) 全都是逆序对：一口气 3 对。代码就一行：
cnt += mid - i + 1; // 左边从 i 到 mid 还剩这么多个，全都比 a[j] 大「左半边有序」是这一行成立的唯一理由。 而那正好是递归已经顺手保证了的 —— 排序成了数逆序对的脚手架。
相等的两个数不构成逆序对（要求是严格大于）。
写成 a[i] < a[j] 的话，相等时会走 else 分支，白白多数一批 —— 答案偏大。
这个错误只有在有重复元素的数据上才会暴露。 所以下面的生成器特意让取值只有 0~5，重复满地都是。 （这个套路第 8 章刚用过一次，它是通用的。）
5 正解：上一章的代码加一行
点「运行 ▶」看结果
把它和第 10 章的 merge.cpp 并排看，差别只有：
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
cnt += mid - i + 1; // ← 新增的唯一一行
tmp[k++] = a[j++];
}点「运行 ▶」看结果
6 单步看「一批一批地数」
盯住红色的那一批：
- 每次从右半边取走一个元素（绿色），左边剩下的那一整批（红色）同时被记账。
- 它们全都比那个绿色元素大 —— 因为左半边是有序的，一个都不用挨个检查。
- 底下的「这一步一口气数了 +k」就是那一行代码的可视化。
暴力是一对一对地数（n² 次），分治是一批一批地数（n log n 次）。
试试把数组改成 5 4 3 2 1（完全降序）：答案是 10，
而 ★ 只会出现四五次 —— 一批就顶好几对。
7 ★ 对拍验证
把「归并」那一栏换成你自己默写的，再点开始。
值得故意写错的：
cnt += mid - i + 1写成cnt += 1→ 退化成只数相邻的，答案偏小cnt += mid - i（少 1）→ 每批少数一对a[i] <= a[j]写成a[i] < a[j]→ 相等时多数，有重复元素就露馅cnt用int→ 小数据对拍全过，大数据溢出（对拍抓不住，只能靠脑子）
8 分治的通用框架
1. 分：把问题切成两个（或多个）规模更小的同类问题
2. 治：递归解决它们（信任！）
3. 合：把子问题的答案拼成原问题的答案 —— 并处理「跨越边界」的那部分第 3 步的「跨越边界」才是每道分治题的真正内容。
| 题目 | 「跨越边界」的部分是什么 |
|---|---|
| 归并排序 | 把两个有序半边合并起来 |
| 逆序对（本章） | 左边一个、右边一个的那些对 |
| 最大子段和（分治版） | 跨过中点的那一段 |
| 平面最近点对 | 一个点在左、一个点在右的那些点对 |
分和治都是套路，合才是每道题不一样的地方。 拿到一道分治题，直接问自己：「跨越中点的那部分怎么算？」
第 38 章的树状数组也能求逆序对，而且代码更短： 从右往左扫，每次问「右边已经出现过多少个比我小的数」。
两种做法都是 O(n log n)，各有各的用处：
- 归并版：不用离散化，思路自洽，适合初学
- 树状数组版：更容易改成「求某个区间里的逆序对」之类的变形
学完第 38 章可以回来用另一种方法再写一遍，然后拿这一章的代码和它对拍 —— 两种完全不同的思路互相验证，这是最踏实的验证方式（第 9 章讲过）。
9 自测
- 洛谷 P1908 逆序对 —— 本章原题，模板。注意开 long long
- 洛谷 P1966 火柴排队 —— NOIP2013。要先想明白「答案等价于求某个排列的逆序对数」，转化是难点
- 洛谷 P1177 排序 —— 上一章那道模板题，这次专门用手写归并交一遍
- 洛谷 P1115 最大子段和 —— 先用 O(n) 的做法过掉，再试着用分治写一遍 —— 练「跨越中点的那部分怎么算」
第 12 章分治进阶：快速幂、二分查找的分治视角、以及「跨越中点」的更多花样。
顺便，你已经具备做第 13 章 DFS 的全部前置知识了 —— 如果想早点摸搜索，可以先跳过去，回头再补第 12 章。