<—点个赞吧QwQ

宣传一下算法基础课整理

$\text{update 2023/02/28}$ 修正了一个很明显的错误。

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i < j$ 且 $a[i] > a[j]$，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

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

数据范围

$1 \le n \le 100000$，
数列中的元素的取值范围 $[1,10^9]$。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

思路

这题暴力会超时，要用归并排序。
一个区间的逆序对数量$=$左边逆序对的数量$+$右边逆序对的数量$+$跨边界的逆序对数量。
前两个很好算，就是跨边界的逆序对数量有些难度。
其实就是在归并过程中，如果有的某一个数大于左边的一个数，就把左边遍历到的数字数量加上。因为左边是有序的，只要右边的数小于左边的一个数，就会小于左边那个数及其后面比它大的同一归并范围的数

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N],tmp[N];
LL merge_sort (int a[],int l,int r) {   //不开long long见祖宗！！！
    if (l == r) return 0;
    int mid = l + r >> 1;
    LL ans = merge_sort (a,l,mid) + merge_sort (a,mid + 1,r);
    int i = l,j = mid + 1,k = 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++],ans += mid - i + 1;
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = 1,j = l;j <= r;i++,j++) a[j] = tmp[i];
    return ans;
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    cout << merge_sort (a,1,n) << endl;
    return 0;
}