归并

个人感觉我这种更好理解吧
核心还是和 y总讲的一样 当第三种情况 即 mid 左右两边的逆序对个数的求法 知道了以后 就行了

#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int arr[N], aux[N];

LL mergeSort(int l, int r) {
    if (l >= r) {
        return 0;
    }
    int mid = l + r >> 1;
    LL res = mergeSort(l, mid) + mergeSort(mid + 1, r);
    for (int i = l; i <= r; i ++) {
        aux[i - l] = arr[i];
    }
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k ++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j ++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i ++;
        } else if (aux[i - l] <= aux[j - l]) {
            arr[k] = aux[i - l];
            i ++;
        } else {
            // 第三种情况 mid 左右的逆序对个数
            arr[k] = aux[j - l];
            j ++;
            res += mid - i + 1;
        }
    }

    return res;

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

    cout << mergeSort(0, n - 1) << endl;
    return 0;
}