解题思路

统计每个数后面比它小的数的总个数。

从右往左扫描，用树状数组维护已经出现过的数，每遇到一个数就查询比它小的有几个。

参考代码

#include <iostream>
using namespace std;

int b[1000001];

void add(int x) {
    for (; x <= 1000000; x += x & -x) b[x]++;
}

int sum(int x) {
    int s = 0;
    for (; x > 0; x -= x & -x) s += b[x];
    return s;
}

int main() {
    int n;
    cin >> n;

    int a[20000];
    for (int i = 0; i < n; i++) cin >> a[i];

    long long s = 0;
    for (int i = n - 1; i >= 0; i--) {
        s += sum(a[i] - 1);
        add(a[i]);
    }

    cout << s << '\n';
    return 0;
}

复杂度分析

O(N log M) 时间，O(M) 空间