对n个数做离散化 然后将其离散化后的相对序在树状数组中修改
每次做比当前数相对位置大的查询(sum(n) - sum(na[i]) 加入ans
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) x&-x;
const int N = 5e5 + 10;
int oa[N], na[N];
int n;
int tree[N];

void add(int d, int x){
    while(x < N){
        tree[x] += d;
        x += lowbit(x);
    }
}

ll sum(int x){
    ll ans = 0;
    while(x > 0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> oa[i];
        na[i] = oa[i];
    }

    sort(oa + 1, oa + 1 + n);
    int cnt = n;

    ll ans = 0;
    for(int i = 1;i <= cnt;i++){
        na[i] = lower_bound(oa + 1, oa + 1 + cnt, na[i]) - oa;
        ans += sum(cnt) - sum(na[i]);
        add(1, na[i]);
    }
    cout << ans << endl;
    return 0;
}