1370 字
4 分钟
归并排序与逆序对统计
一、归并排序（1‑based 闭区间写法）
核心框架
void merge(int l, int mid, int r) { vector<int> left(a + l, a + mid + 1); // 拷贝左半 [l, mid] int i = 0, j = mid + 1, k = l;
while (i < left.size() && j <= r) { if (left[i] <= a[j]) a[k++] = left[i++]; else a[k++] = a[j++]; } while (i < left.size()) a[k++] = left[i++]; // 右半剩余已在正确位置，无需处理}
void msort(int l, int r) { if (l >= r) return; // 长度 ≤1 终止 int mid = (l + r) / 2; msort(l, mid); msort(mid + 1, r); merge(l, mid, r);}关键细节
- 递归终止条件：闭区间
[l, r]长度为r - l + 1，l >= r时长度为 0 或 1，直接返回。 - 临时数组：只拷贝左半部分，右半留在原数组操作，避免被覆盖。
- 稳定性：比较用
<=，相等时左先，保持原序。 - 右半剩余：主循环结束后，若右半有剩余已在
a[k..r]中正确就位（数学可证k == j），无需再拷贝。
易错点
| 错误写法 | 正确写法 | 原因 |
|---|---|---|
if (r - l <= 1) return; | if (l >= r) return; | 1‑based 下长度为 2 时差值为 1，不应终止 |
while (i <= mid && j <= r) 中用 ans[i-k] | 用 ans[i-l] 或独立 i | k 和 i 不同步，下标会算错 |
主循环用 || | 用 && | || 会导致一方走完后访问越界元素 |
merge 后不写回 a | 在 merge 内直接写 a[k++] = ... | 否则排序结果未保留 |
二、统计逆序对
核心思想
在合并两个已排序的区间时，若 left[i] > a[j]，由于左半区间升序，left[i..end] 中所有元素都大于 a[j]，它们都与 a[j] 构成逆序对，一次性累加 left.size() - i 个。
完整代码
#include <bits/stdc++.h>using namespace std;
const int MAXN = 100005;int a[MAXN], n;
long long merge_and_count(int l, int mid, int r) { vector<int> left(a + l, a + mid + 1); long long inv = 0; int i = 0, j = mid + 1, k = l;
while (i < left.size() && j <= r) { if (left[i] <= a[j]) { a[k++] = left[i++]; } else { inv += left.size() - i; // 批量统计 a[k++] = a[j++]; } } while (i < left.size()) a[k++] = left[i++];
return inv;}
long long count_inversions(int l, int r) { if (l >= r) return 0; int mid = (l + r) / 2; long long inv = 0; inv += count_inversions(l, mid); inv += count_inversions(mid + 1, r); inv += merge_and_count(l, mid, r); return inv;}关键点
- 为什么是
left.size() - i？ 左半已升序，left[i] > a[j]⇒ 从 i 到末尾的所有元素都 >a[j]。 - 数据类型：最大逆序对数
n*(n-1)/2可达~5e9（n=1e5），必须用long long。 - 相等处理：用
<=保证相等时不统计，符合严格逆序对定义（i < j且a[i] > a[j]）。 - 递归执行顺序：左子树 → 右子树 → 合并（后序遍历）。
思维进阶：为什么左右已经有序？
递归的自底向上过程保证了有序：
[3,1,4,2] ← 合并时左右已有序 / \ [3,1] [4,2] ← 合并时左右已有序 / \ / \ [3] [1] [4] [2] ← 单元素天然有序每一层的 merge 执行时，左右子区间已经通过递归完成了排序。
三、推广：处理偏序关系
从逆序对到二维偏序
逆序对本质是二维偏序问题：统计满足 i < j 且 a[i] > a[j] 的点对。
- 第一维（下标）：归并分治天然保证左 < 右。
- 第二维（值）：在 merge 中比较并批量统计。
其他偏序变体
| 问题 | 条件 | 处理方法 |
|---|---|---|
| 顺序对 | i < j 且 a[i] < a[j] | 可在归并中统计，或转求逆序对 |
| 非严格逆序对 | i < j 且 a[i] >= a[j] | 将 <= 改为 < 再统计 |
| 有条件逆序对 | i < j 且 a[i] > a[j] + k | merge 中用双指针滑动满足条件的范围 |
CDQ 分治（三维偏序）
处理形如 i < j, a[i] > a[j], b[i] < b[j] 的三维偏序：
- 按第一维排序（或分治）。
- 归并第二维，同时用树状数组维护第三维统计。
CDQ 分治是归并分治处理偏序的终极形态，是离线处理多维偏序问题的利器。
四、常见调试技巧
用 cerr 跟踪递归过程
long long count_inversions(int l, int r, int dep = 0) { string indent(dep * 2, ' '); cerr << indent << "进入 [" << l << "," << r << "]" << endl; if (l >= r) { cerr << indent << "返回 0" << endl; return 0; } int mid = (l + r) / 2; long long inv = count_inversions(l, mid, dep+1); inv += count_inversions(mid+1, r, dep+1); inv += merge_and_count(l, mid, r); cerr << indent << "返回 " << inv << endl; return inv;}cerr 输出到 stderr，不影响 cout 的答案，适合调试时保留。
小数据手算验证
用 [3,1,4,2] 手动模拟递归树，确保每个 merge 中的逆序对累加正确。
五、我的代码进化史（从错误到正确）
下面记录了我从思路到手到写出正确代码的全过程，每个版本都犯过不同的错，但也一步步逼近正确答案。
版本 1：思路有了，但全是坑
vector<int> ans;void merge(int l, int mid, int r) { int i = l, j = mid + 1; while (i <= mid || j <= r) // 错误1：用 ||，越界后还在访问 { if(a[i]<=a[j]) // 越界后 a[i] 或 a[j] 是脏数据 ans.push_back(a[i]), i++; else ans.push_back(a[j]), j++; }}void msort(int l, int r) { if (r - l <= 1) return; // 错误2：1-based下长度2直接返回 int mid = l + (r - l) / 2; msort(l, mid); msort(mid + 1, r); merge(l, mid, r); // 错误3：merge结果存在ans，没写回a}问题：
||导致一方走完还在访问已越界的元素- 没有处理剩余元素（需要先用
&&循环，再用两个while分别收尾） ans全局变量不断追加，从未清空也从未写回原数组- 递归终止条件导致长度为 2 的区间无法排序
版本 2：尝试改进，引入新 bug
void merge(int l, int mid, int r) { int i = l, j = mid + 1; vector<int> ans(a + l, a + mid + 1); int k = l; while (i <= mid && j <= r) { if (ans[i-k] <= a[j]) // bug：i-k 的索引方式错误！ a[k++]=ans[i-k], i++; else a[k++]=a[j], j++; }}void msort(int l, int r) { if (r - l <= 1) return; // 同样的终止条件错误 ...}进步：用了临时数组 vector<int> ans(a + l, a + mid + 1)，思路已正确。
新 bug：ans[i-k] 中 k 和 i 变化不同步——当 else 分支执行时 k 增加但 i 不变，i-k 会变负，下标完全乱掉。
版本 3：越来越接近
void merge(int l, int mid, int r) { int i = l, j = mid + 1; vector<int> ans(a + l, a + mid + 1); int k = l; while (i <= mid && j <= r) { if (ans[i-l] <= a[j]) // 修正为 i-l，这次对了 a[k++]=ans[i-l], i++; else a[k++]=a[j], j++; } while(i<=mid) a[k++] = ans[i - l]; // 左剩余处理正确}void msort(int l, int r) { if (r - l <= 1) return; // 终止条件还是错的 ...}进步：ans[i-l] 是正确的索引方式。
遗留问题：递归终止条件依然没改过来。
版本 4：最终正确版本
将 msort 的终止条件改为 if (l >= r) return;，所有问题解决。
关键教训
| 错误类型 | 次数 | 如何避免 |
|---|---|---|
| 递归终止条件写错 | 3 次 | 闭区间 [l,r] 牢记 l>=r 才终止 |
临时数组索引混用 i-k | 1 次 | 给 left 单独设下标 i，从 0 开始，不与 k 耦合 |
循环条件用 || 而非 && | 1 次 | 牢记：双指针先 && 走完，再单独处理剩余 |
| merge 结果未写回 | 1 次 | merge 内直接操作 a[k]，不再用全局变量 |
这些错误看似低级，但每踩一次都在加深理解。能写出最终的正确代码，正是因为前面的每个错误都让我更清楚边界在哪。
六、心得总结
- 归并排序是分治思想的典型应用：分解 → 递归 → 合并。
- 逆序对统计是归并排序的自然拓展：利用有序性批量统计，不增加时间复杂度。
- 递归执行顺序 = 后序遍历：左 → 右 → 根（合并），理解了这点递归不再抽象。
- 从思路到代码的桥梁：
- 先写伪代码明确每一步。
- 注意边界条件（递归终止、指针范围）。
- 用调试输出验证脑内模拟。
- 归并分治可推广到偏序问题：逆序对是入门特例，CDQ 分治是进阶方向。
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐