解题思路

用到了归并排序的思想，在此基础上，将逆序对分为3大类：
① 逆序对的两个数都在左边区间；
② 逆序对的两个数都在右边区间；
③ 逆序对的两个数分布在左右两个区间；

在进行归并排序的过程中，每次要将q[j]输出的时候，顺带着输出sj = mid - i + 1，表示在L区间中，所有大于R区间中第j个数的所有数的数量。

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n ;
int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1; // 右移1等价于整除以2
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    // 归并的过程
    int k = 0, i = l, j = mid + 1;
    while ( i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            tmp[k ++ ] = q[j ++ ];
            res += mid - i + 1;
        }
    // 扫尾
    while(i <= mid) tmp[k ++ ] = q[i ++ ];
    while(j <= r) tmp[k ++ ] = q[j ++ ];

    // 物归原主 i循环原数组，q循环临时数组
    for (int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i];

    cout << merge_sort(0, n - 1) << endl;

    return 0;
}