逆序对

洛谷-P1908-逆序对

分析

见《进阶指南》第204页。

实现

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

typedef long long LL;
const int N = 500010;
int n, a[N];
int m, nums[N];
int c[N];

void discrete () {
    for (int i = 1; i <= n; ++ i) nums[i] = a[i];
    sort(nums + 1, nums + n + 1);
    m = unique(nums + 1, nums + n + 1) - (nums + 1);
}
int query (int x) {
    return lower_bound(nums + 1, nums + m + 1, x) - nums;
}
int lowbit (int x) {
    return x & -x;
}
void add (int idx, int val) {
    while (idx <= n) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
int sum (int idx) {
    int res = 0;
    while (idx >= 1) {
        res += c[idx];
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    discrete();
    for (int i = 1; i <= n; ++ i) a[i] = query(a[i]);

    LL res = 0;
    for (int i = n; i >= 1; -- i) {
        res += sum(a[i] - 1);
        add(a[i], 1);
    }
    printf("%lld", res);
    return 0;
}