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