【输入】

第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。

【输出】

所有逆序对总数。

【输入样例】

4
3
2
3
2

【输出样例】

3

【提示】

解题思路

求逆序对的数目可以用归并排序来解决。在归并排序的过程中，将原始序列递归地划分成若干个子序列，每次合并两个有序子序列时，可以通过统计左右两个子序列之间的逆序对数量来计算当前子序列的逆序对数量。

参考答案

#include "iostream"
using namespace std;

int num[100000];
//临时数组
int tmp[100000];

//归并排序
long long merge(int l, int r) {
    if (l + 1 == r){
        return 0;
    }
    int m = (l + r) / 2;
    //先分
    long long res = merge(l, m) + merge(m, r);
    //后合
    for (int i = l, j = m, k = l; k < r; k++) {
        //左边数组中的小，直接排
        if (j == r || (i < m && num[i] <= num[j])) {
            tmp[k] = num[i];
            i++;
        } else {
            //否则右边数组中的小，产生逆序对
            tmp[k] = num[j];
            j++;
            //计算逆序对数量
            res += m - i;
        }
    }
    //将排好顺序的数据复制回num数组中
    for (int k = l; k < r; k++){
        num[k] = tmp[k];
    }
    return res;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> num[i];
    }
    cout << merge(0, n) << endl;
    return 0;
}

//常规解决方法会timeout
int main_1(){
    int n;
    cin>>n;
    int* a = new int[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int nums = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]){
                nums++;
            }
        }
    }
    cout<<nums<<endl;
    return 0;
}