如何计算逆序对的数量？

4.Acwing基础课第788题-简单-逆序对的数量 题目描述 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。 逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。 输入格式 第一行包含整数 nn，表示数列的长度。 第二行包含 nn 个整数，表示整个数列。 输出格式 输出一个整数，表示逆序对的个数。 数据范围 1≤n≤100000 数列中的元素的取值范围 [1,109]。 输入样例 6 2 3 4 5 6 1 输出样例 5 思路解析： 算法：归并排序 （ Quick Sort ） 时间复杂度：O(nlog(n)) 解题思路： 归并排序是一种分治算法。它将一个大的数组不断分成两个子数组，递归地对两个子数组进行排序，然后再将排好序的子数组合并起来。 代码： // 包含C++标准输入输出流头文件，用于cout输出 #include <iostream> // 使用标准命名空间，避免每次调用标准库都写std:: using namespace std; // 给long long长整型起别名LL // 逆序对数量可能极大，int会溢出，必须用long long存储 typedef long long LL; // 定义数组最大长度：1e5+10（100010），满足题目数据范围，+10防止数组越界 const int N = 1e5 + 10; // a[]：存储原始输入的数组 // tmp[]：归并排序的**临时辅助数组**，用于暂存合并后的有序元素 int a[N], tmp[N]; /** * @brief 归并排序函数，同时统计区间[l, r]内的逆序对数量 * @param q 待排序/统计的数组 * @param l 区间左边界 * @param r 区间右边界 * @return LL 当前区间内的逆序对总数 */ LL merge_sort(int q[], int l, int r) { // 递归终止条件：区间只有一个数 或 无数据，没有逆序对，返回0 if (l >= r) return 0; // 计算区间中点：等价于 (l + r) / 2，位运算>>1效率更高 int mid = l + r >> 1; // 递归处理左半区间 [l, mid] + 右半区间 [mid+1, r] // res 累加：左区间内部逆序对 + 右区间内部逆序对 LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // 双指针初始化： // i：指向左区间的起始位置 l // j：指向右区间的起始位置 mid+1 // k：指向临时数组tmp的起始位置 0 int k = 0, i = l, j = mid + 1; // 核心：合并两个有序区间，同时统计**跨区间的逆序对** while (i <= mid && j <= r) { // 左区间当前数 ≤ 右区间当前数：无逆序对，直接放入临时数组 if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; // 左区间当前数 > 右区间当前数：**找到逆序对** else { // 关键！左区间中从i到mid的所有数，都比q[j]大 // 逆序对数量 += mid - i + 1 res += mid - i + 1; // 将右区间当前数放入临时数组 tmp[k ++ ] = q[j ++ ]; } } // 左区间还有剩余元素（全部有序），直接复制到临时数组 while (i <= mid) tmp[k ++ ] = q[i ++ ]; // 右区间还有剩余元素（全部有序），直接复制到临时数组 while (j <= r) tmp[k ++ ] = q[j ++ ]; // 把临时数组tmp中排好序的元素，复制回原数组q的[l, r]区间 for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; // 返回当前区间的总逆序对数量（内部+跨区间） return res; } int main() { // n：数组元素个数 int n; // 输入n scanf("%d", &n); // 循环输入n个元素，存入数组a for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); // 调用归并排序，输出整个数组的逆序对总数 cout << merge_sort(a, 0, n - 1) << endl; // 程序正常结束 return 0; } 一、主题与核心目标 讲解经典算法题「逆序对的数量」，摒弃低效的暴力解法，重点传授基于归并排序的分治求解方法，让学习者掌握高效算法思路，并深入理解分治思想的实际应用。 二、逆序对定义与题目规则 逆序对概念：给定序列中，下标满足 i<j 且对应元素 a[i]>a[j] 的数对，即为逆序对； 举例说明：序列 [3,1,2] 包含 (3,1)、(3,2) 两个逆序对，答案为 2； 输入输出：输入序列长度 n 和整数序列，输出逆序对总数； 数据限制：n 最大为 10⁵，对算法效率有硬性要求。 三、暴力解法分析（淘汰方案） 实现思路：双重循环遍历所有数对，逐一判断并统计逆序对； 致命缺陷：时间复杂度为 O(n²)，当 n=10⁵时，运算量达 10¹⁰次，远超计算机每秒 10⁸次的运算极限，必然超时，无法通过测试。 四、核心解题思想：分治 + 归并排序 分治核心逻辑：将整个序列的逆序对拆分为三部分求和：左半区间内部逆序对 + 右半区间内部逆序对 + 左右区间跨元素逆序对； 归并排序适配性：递归将序列拆分至单个元素（单元素无逆序对），自下而上合并有序子区间，利用区间有序性高效统计跨区间逆序对，这是算法的核心关键。 五、算法完整步骤 视频将算法拆解为递归拆分、合并统计、返回结果三步，逻辑清晰： 递归拆分：定义merge_sort递归函数，以区间[l,r]为处理范围；终止条件l>=r（返回 0）；计算中点mid拆分区间，递归求解左右子区间的逆序对数量； 合并统计：双指针遍历左右有序子区间，比较元素大小： 左元素≤右元素：不构成逆序对，直接合并； 左元素 > 右元素：左区间剩余所有元素均大于右元素，一次性统计mid-i+1个逆序对； 用临时数组存储合并结果，最终复制回原数组，保证上层递归的区间有序性； 返回结果：递归函数最终返回总逆序对数量。 六、代码实现与关键细节 提供 C++ 完整可运行代码，并强调 4 个核心细节，避免程序出错： 数据类型：必须用long long存储结果，防止数值溢出（10⁵长度的序列逆序对数量超 int 范围）； 效率优化：用位运算l + r >> 1计算中点，效率高于普通除法； 临时数组：合并时必须用临时数组，防止覆盖原数组未比较元素； 数据回写：合并完成后将有序序列复制回原数组，保证递归正确性。 七、算法效率分析 时间复杂度为 O(nlogn)：递归拆分层数为logn，每一层合并需遍历全数组（O (n)），该复杂度完美适配 n=10⁵的数据范围。 八、高频问题答疑 针对学习者最易困惑的 3 个问题逐一解答： 递归后区间始终有序：归并排序从单元素（天然有序）开始合并，合并后的区间保持有序； 统计公式mid-i+1的原理：左区间有序，a[i]>a[j]时，i 到 mid 的所有元素都能与 a [j] 构成逆序对； 不推荐快速排序：快排无法利用有序性高效统计跨区间逆序对，实现复杂且效率不稳定。 九、总结 本题的核心是借助归并排序的分治思想和区间有序性，将暴力解法的 O (n²) 复杂度优化为 O (nlogn)；通过「拆分问题 - 递归求解 - 合并统计」的流程，高效解决逆序对统计问题，同时夯实分治思想的应用基础。 ✅ 归并排序求逆序对的本质： 把数组拆成两个子区间 递归算出两个区间内部的逆序对 利用「两个区间已经有序」的特点，在合并时快速算出所有跨区间逆序对 三者相加 = 总逆序对数量 最核心的本质：正是依靠对比、合并两个有序子区间，才能高效算出逆序对！ 总结 从基础概念、错误解法排除，到核心思想、算法步骤、代码实现、效率分析，再到疑难解答，形成闭环讲解；最终让学习者不仅会写代码，更能理解分治 + 归并排序解决逆序对问题的底层逻辑。