树状数组+离散化求逆序对

#include<cstdio>
#include<algorithm>
typedef long long LL;

int n,tot0,a[500005],b[500005];

LL ans;

struct BIT{
    int c[500005];
    inline int lowbit(int x){return x&(-x);}
    inline void add(int k,int x){
        while(k<=n){
            c[k]+=x;
            k+=lowbit(k);
        }
    }
    inline int query(int k){
        int fuck=0;
        while(k){
            fuck+=c[k];
            k-=lowbit(k);
        }
        return fuck;
    }
}T;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
    }
    for(int i=n;i>=1;i--){
        if(a[i]==1){
            ans+=tot0;
            T.add(a[i],1);
        }
        else if(a[i]==0){
            tot0++;
        }
        else{
            ans+=T.query(a[i]-1);
            T.add(a[i],1);
        }
    }
    printf("%lld\n",ans);
}

求的是1≤n≤5×10^5，0≤a[i]≤10^9。

如果a[i]小于等于0的话其实可以全局加上某一个数字，变成正的，要不然szsz干不了他

像我这样智商不够归并排序的蒟蒻只能靠数据结构来凑啦

树状数组+离散化求逆序对

原文：https://www.cnblogs.com/Y15BeTa/p/11846593.html