【模板】逆序对

发布于 2022-07-26  5 次阅读


#include <bits/stdc++.h>

#define int long long
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, ans, a[N];

int my_sort(int q[], int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) >> 1;
    int ans = my_sort(q, l, mid) + my_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++], ans += mid - i + 1;
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
    return ans;
}

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
    printf("%lld\n", my_sort(a, 1, n));
    return 0;
}