P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树状数组可以干这个事情

树桩数组维护一个下标啦

然后离散化一下，sort，unique，二分确定每一个数在新序列的下标

也就是第i个数大小的排名。

然后算一下有多少个数，拍在他前面且大小排名在它之前。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long 
using namespace std;
int n;
int a[5000001];
int b[5000001];
int id[5000001];
int tr[5000001];
inline int lowbit(int x){
    return x&(-x);
}
void add(int x){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]++;
    }
}
int query(int x){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;

}

signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(a+1,a+n+1);
    int nn=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;++i){
        id[i]=upper_bound(a+1,a+n+1,b[i])-a-1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        ans+=i-1-query(id[i]);
        add(id[i]);
    }
    cout<<ans;
    return 0;
}