$\Huge\color{orchid}{点击此处获取更多干货}$

归并排序

逆序对统计不一定非要利用归并排序，另外一种方法在提高篇里介绍
构成逆序对的两个元素相对于中点的分布情况一共有以下三种：
1. 两元素全都在左侧
2. 两元素全都在右侧
3. 一个元素在左侧，一个元素在右侧

先看情况3，可以利用归并排序的“合并”过程，如果左边有一个元素比右边的大，利用两段的有序性，可以得知左半区内从当前位置一直到中点的元素都比右边的那个元素大，左边的这些元素和右边的那个元素都可以一一形成逆序对。请看下图：

以上就是情况3的演示，至于情况1和2，可以借助归并排序的递归分治来统计

C++ 代码

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int* arr = new int[n], * cache = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    //size_t就是unsigned long long，标准库已经自动定义好
    function<size_t(int, int)> reversePairs
        = [&](int left, int right)->size_t {
        if (left >= right) return size_t(0);
        int mid = (left + right) / 2;
        //先利用递归统计情况1和2
        size_t cnt = reversePairs(left, mid) + reversePairs(mid + 1, right);
        //然后开始统计情况3（只需要在归并排序基础上多一条累加即可）
        int ls = left, rs = mid + 1, id = 0;
        while (ls <= mid && rs <= right) {
            if (arr[ls] <= arr[rs]) {
                cache[id] = arr[ls];
                ls++;
            }
            else {
                cache[id] = arr[rs];
                rs++;
                //左半边直到中点，长度为mid - ls + 1
                cnt += size_t(mid - ls + 1);
            }
            id++;
        }
        while (ls <= mid) {
            cache[id] = arr[ls];
            ls++;
            id++;
        }
        while (rs <= right) {
            cache[id] = arr[rs];
            rs++;
            id++;
        }
        copy(cache, cache + id, arr + left);
        return cnt;
    };
    cout << reversePairs(0, n - 1) << endl;
    delete[] arr;
    delete[] cache;
    return 0;
}