P1908 逆序对

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
int a[MAXN], tmp[MAXN];
long long ans = 0;

// 归并排序：合并时统计「跨越左右两半」的逆序对
void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            ans += mid - i + 1;     // 左半剩下的都大于刚取出的这个数
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

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