【题目来源】
AcWing：788. 逆序对的数量 - AcWing题库
【题目描述】
给定一个长度为 \(n\) 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 \(i\) 个和第 \(j\) 个元素，如果满足 \(i<j\) 且 \(a[i]>a[j]\)，则其为一个逆序对；否则不是。
【输入】
第一行包含整数 \(n\)，表示数列的长度。
第二行包含 \(n\) 个整数，表示整个数列。
【输出】
输出一个整数，表示逆序对的个数。
【输入样例】
6
2 3 4 5 6 1
【输出样例】
5
【解题思路】
【算法标签】
《AcWing 788 逆序对的数量》 #归并排序#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef long long LL; // 定义长整型别名，用于存储大数
const int N = 100010; // 定义数组最大容量int n; // 数组元素个数
int q[N]; // 存储待排序的数组
int tmp[N]; // 归并排序使用的临时数组// 归并排序函数，同时计算逆序对数量
LL merge_sort(int l, int r) {// 递归终止条件：区间长度小于1时不需要排序，逆序对数量为0if (l >= r) return 0;// 计算中点int mid = (l + r) >> 1; // 等价于(l + r)/2// 递归处理左右两半，并累加逆序对数量LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);// 归并过程int k = 0; // 临时数组指针int i = l; // 左半部分指针int j = mid + 1; // 右半部分指针while (i <= mid && j <= r) {if (q[i] <= q[j]) {tmp[k++] = q[i++]; // 左半元素较小，直接放入} else {tmp[k++] = q[j++]; // 右半元素较小，产生逆序对res += mid - i + 1; // 统计逆序对数量}}// 处理剩余元素while (i <= mid) tmp[k++] = q[i++]; // 左半剩余元素while (j <= r) tmp[k++] = q[j++]; // 右半剩余元素// 将临时数组内容复制回原数组for (int i = l, j = 0; i <= r; i++, j++) {q[i] = tmp[j];}return res; // 返回当前区间的逆序对总数
}int main() {// 输入数据cin >> n;for (int i = 0; i < n; i++) cin >> q[i];// 调用归并排序并输出逆序对总数cout << merge_sort(0, n - 1) << endl;return 0;
}
【运行结果】
6
2 3 4 5 6 1
5