4.Acwing基础课第788题-简单-逆序对的数量

4.Acwing基础课第788题-简单-逆序对的数量

题目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式

第一行包含整数 nn，表示数列的长度。
第二行包含 nn 个整数，表示整个数列。
输出格式

输出一个整数，表示逆序对的个数。
数据范围

1≤n≤100000
数列中的元素的取值范围 [1,109]。
输入样例

1. 6
2. 2 3 4 5 6 1

复制代码

输出样例

1. 5

复制代码

思路解析：

算法：归并排序 （ Quick Sort ）

时间复杂度：O(nlog(n))

解题思路：

归并排序是一种分治算法。它将一个大的数组不断分成两个子数组，递归地对两个子数组进行排序，然后再将排好序的子数组合并起来。

代码：

[code]// 包含C++标准输入输出流头文件，用于cout输出#include // 使用标准命名空间，避免每次调用标准库都写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