逆序对的数量

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;

struct Node {
    int val, id;
    bool operator < (const Node& a) const {
        return val == a.val ? id < a.id : val < a.val;
    }
}a[N];
int n, tree[N];
ll res;

inline int lowbit(int x) { return x&-x; }

inline void update(int x, int c) {
    for(int i = x; i <= n; i += lowbit(i)) tree[i] += c;
}

inline int query(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tree[i];
    return res;
}

int main(int argc, char **argv) {
    cin.tie(0)->sync_with_stdio(false);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].val, a[i].id = i;
    sort(a+1, a+1+n);
    for(int i = 1; i <= n; i++) {
        update(a[i].id, 1);
        res += i-query(a[i].id);
    }
    cout << res << '\n';
    
    return 0;
}