逆序对+离散化

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn],c[maxn];
struct dd {
    int x,id;
    dd(int xx=0,int yy=0):x(xx),id(yy) {
    }
    bool operator <(const dd&aa)const {
        return x<aa.x;
    }
};
dd b[maxn];
int lowbit(int x) {
    return x&(-x);
}
int n;
int add(int x,int y) {
    for(int i=x; i<=1e6+10; i+=lowbit(i)) {
        c[i]+=y;
    }
}
long long ask(int x) {
    long long ans=0;
    for(int i=x; i>0; i-=lowbit(i))
        ans+=c[i];
    return ans;
}
int main() {
//    freopen("2.in","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>b[i].x;
        b[i].id=i;
        //cin>>a[i];
    }
    sort(b+1,b+1+n);
    int now=0,nub=0;
    for(int i=1; i<=n; i++) {
        if(b[i].x!=nub) {
            now++;
            a[b[i].id]=now;
            nub=b[i].x;
        } else {
            a[b[i].id]=now;
            nub=b[i].x;
        }
    }
    long long ans=0;
    for(int i=n; i>=1; i--) {
        add(a[i],1);
        ans+=ask(a[i]-1);

    }
    printf("%lld\n",ans);
    //十年oi一场空，不开longlong见祖宗 
    return 0;
}

记得输出也要用long long