题目描述

（原题 ）

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

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

输入格式
第一行包含整数n，表示数列的长度。

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

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

数据范围
1≤n≤100000

输入样例

6
2 3 4 5 6 1

输出样例

5

算法

归并排序 $O(nlog2n)$

归并算法的思路，请见归并排序 。这道题是归并排序的变形，很巧妙，看了y总的讲解才知道。具体讲代码注释。

参考文献

y总视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//答案数据会超出int范围，用longlong存储
typedef long long LL;
const int N = 1e5 + 10;
int q[N];
int temp[N];


LL mergeSort(int q[],int l ,int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    //答案等于左右半边之和。
    LL res = mergeSort(q,l,mid) + mergeSort(q,mid + 1 ,r);
    int k = 0 , i = l , j = mid +  1;
    while(i <= mid && j <= r){
    //注意这里就要加上=号,因为逆序对是前面的数严格大于后面的数! 之前的归并排序并不需要加,
        if(q[i] <= q[j]) temp[k++] = q[i++];
        else{
        /*
         这道题是归并的变形，根据逆序对的定义，我们可以发现排序的第二种情况正好就是逆序对：
         左半边的起始值（及以后）都大于右半边的起始值。 所以直接用左半边的右边界mid - i（起始处）+1
         就可以得到当前逆序对的数量。

        */
            res += mid - i + 1;

            temp[k++] = q[j++];
        }
    }

    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    for(int i = l , j = 0; i <= r ;i++ , j++)q[i] = temp[j]; 
    return res;
}

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