逆序对的数量

题目描述

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

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

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

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

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

数据范围
1≤n≤100000

输入样例

6
2 3 4 5 6 1

输出样例

5

时间复杂度 O(n * logn)

参考文献 数据结构（C++版）邓俊辉 第三版、大佬yxc的算法视频

C++ 代码

#include <iostream>
using namespace std;
typedef long long LL;
// 所有区间都是下闭上开区间
void merge ( int* a, int lo, int mi, int hi, LL& res ) {    
   // 将a数组看做两段 数组A和数组C
   // 复制划分得到的左边数组A到新的数组B中
   int* A = a + lo; 
   int lb = mi - lo; 
   int* B = new int[lb]; 
   for ( int i = 0; i < lb; ++i ) B[ i ] = A[ i ]; 

   int lc = hi - mi; 
   int* C = a + mi;
   int i = 0, j = 0, k = 0;
   while ( i < lb && j < lc ) {
       // B数组中保存的是左半段数据，C数组中保存的是右半段数据。并且它们各自有序
       // 如果B[i]不大于C[j]，那么B数组在区间[0,i]上的任意一个元素都不大于C[j]，
       // 也就是此时，B数组在区间[0, i]上的任意一个元素都不可以与C[j]构成逆序对
       // 否则，由于数组B、C各自有序，那么B数组在区间[i,lb)上的任意一个元素都大于C[j]，
       // 也就是此时，B数组在区间[i, lb)上的任意一个元素都可以与C[j]构成逆序对，
       // 这些逆序对的数量是：lb - 1 - i + 1, 由于区间是：[i, lb), 也可以这样计算：lb - i
       // 以上断言依靠的是数组B、C的单调性特性
       if ( B[ i ] <= C[ j ] ) A[ k++ ] = B[ i++ ];
       else {
          res += lb - i;
          A[ k++ ] = C[ j++ ];
       }
   }
   while ( i < lb ) A[ k++ ] = B[ i++ ];
   while ( j < lc ) A[ k++ ] = C[ j++ ];

   delete []B;

} //归并后得到完整的有序数组[lo, hi)

LL mergeSort ( int* a, int lo, int hi ) {     // 0 <= lo < hi <= n
   if( hi - lo < 2 ) return 0;   //单个元素区间自然有序

   int mi = lo + ( ( hi - lo ) >> 1 );  // 以中点为界

   // 逆序对的分布情况：
   // (1) 都在a[ mi ]的左边
   // (2) 都在a[ mi ]的右边
   // (3) 各自在a[ mi ]的两侧

   // 计算逆序对分布在a[ mi ]同侧的数量
   LL res = mergeSort ( a, lo, mi ) + mergeSort ( a, mi, hi );
   merge ( a, lo, mi, hi, res ); // 归并

   return res;
}

int main ( ) {
    int n;
    cin >> n;

    int a[ n ];
    for ( int i = 0; i < n; ++i ) cin >> a[ i ];
    cout << mergeSort ( a, 0, n ) << endl;

    return 0;
}

YXC版

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], n;

LL msort(int l, int r) {
    if(r - l < 1) return 0;
    int m = l + r >> 1;
    LL ans = msort(l, m) + msort(m + 1, r);
    int i = l, j = m + 1;
    for(int k = l; k <= r; k++) {
        if(i <= m && a[i] <= a[j] || j > r) b[k] = a[i++];
        else {
            ans += m - i + 1;
            b[k] = a[j++];
        }
    }
    for(int k = l; k <= r; k++) a[k] = b[k];
    return ans;
}

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