P1908 逆序对

给定一个数组，求逆序对的个数。
($n\le 5\times {10}^5,a_i\le {10}^9$)

Solution

树状数组

pair<int, int> a[500010];
int n, ranks[500010], tr[500010];
int lowbit(int x) {
    return x & -x;
}
void change(int x, int k) {
    while (x <= n)tr[x] += k, x += lowbit(x);
}
int query(int x) {
    int ans = 0;
    while (x)ans += tr[x], x -= lowbit(x);
    return ans;
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i].first;a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1;i <= n;i++) {
        ranks[a[i].second] = i;
    }
    ll ans = 0;
    for (int i = 1;i <= n;i++) {
        change(ranks[i], 1);
        ans += i - query(ranks[i]);
    }
    /*等价于上面的
	for (int i = n;i >= 1;i--) {
	ans += query(ranks[i] - 1);
	change(ranks[i], 1);
    }
    */
    cout << ans << '\n';
}