思路

思路：分治，把数组分成两半，分别排序，逆序对由三部分构成，左半边的逆序对 + 右半边的逆序对 + 跨过两遍的逆序对。边界：当只有一个元素时，逆序对为0（显然），因为左右半边如果排序好，那么可以用合并没打出现又q[i] > q[j]则说明有mid - i + 1个逆序对，因为有序！所以可以使用归并排序来处理。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int tmp[N];
int merge_sort(int q[], int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else res += mid - i + 1, tmp[k++] = q[j++];
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(i = 0, j = l; i < k; i++, j++) {
        q[j] = tmp[i];
    }
    return res;
}

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