题解：树状数组求逆序对

/*
 *  @filename:~/Documents/workspace/vscode_space
 *  @author: Ly_boy
 *  @date: 2024-11-27 10:02:52  星期三
 *  @version: V1.0.1
 *  @description: Copyright (cpp) 2024 by Ly_boy, All Rights Reserved.
 */
#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

const int N = 5000005;
int c[N];
int n;
pair<int, int> a[N]; // 第一个元素是值，第二个元素是原始索引

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

void add(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        c[i] += k;
    }
}

int query(int x)
{
    int s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
    {
        s += c[i];
    }
    return s;
}

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

    long long ans = 0;
    for (int i = n; i >= 1; i--)
    {
        ans += query(a[i].second - 1);
        add(a[i].second, 1);
    }
    printf("%lld\n", ans);
    return 0;
}