题目描述

本题的题解就是再归并排序的基础上加上了逆序对的判断，很简单
还要注意递归的时候，结果是如何返回的

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int q[N],n,temp[N];

LL merge_sort(int i , int j){
    LL cnt = 0;
    if(i >= j) return 0;
    int mid = (i + j) / 2;
    cnt += merge_sort(i,mid);
    cnt += merge_sort(mid + 1,j);

    int l = i,r = mid + 1;
    int k = 0;
    while(l <= mid && r <= j){
        if(q[l] <= q[r]) temp[k++] = q[l++];
        else{
            temp[k++] = q[r++];
            cnt += (mid - l + 1);
        }
    }
    while(l <= mid) temp[k++] = q[l++];
    while(r <= j) temp[k++] = q[r++];
    for(l = i,r = 0;l <= j;++l,++r){
        q[l] = temp[r];
    }

    return cnt;
}

int main(){
    cin >> n;
    for(int i = 0;i < n;++i)
        cin >> q[i];
    cout << merge_sort(0,n-1);
    return 0;
}