题解

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

using i64 = long long;

constexpr int N = 5e5;

template<class T>
class FenwickTree {
private:
int n;
vector<T> sum;
int lowbit(int x) {return x & -x;}
public:
FenwickTree(int n = 0) : n(n), sum(n + 1) {}

void add(int x, T d) {
    for (; x <= n; x += lowbit(x))
        sum[x] += d;
}

T ask(int x) {
    T res = 0;
    for (; x; x -= lowbit(x))
        res += sum[x];
    return res;
}

};

int main() {
cin.tie(nullptr)->sync_with_stdio(false);
FenwickTree<int> cnt(N);
int n; cin >> n;
i64 res = 0;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
res += cnt.ask(x - 1);
cnt.add(x, 1);
}
cout << res << '\n';
return 0;
}