逆序对

#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN=2e5+25;
ll n,ans;
ll x[MAXN];
void mergesort(ll la,ll ra,ll lb,ll rb){
    ll i=la,j=lb,cnt=0;
    ll a[MAXN];
    while(i<=ra&&j<=rb){
        if(x[i]<=x[j]) a[++cnt]=x[i++];
        else{
            a[++cnt]=x[j++];
            ans+=ra-i+1;
        }
    }
    while(i<=ra) a[++cnt]=x[i++];
    while(j<=rb) a[++cnt]=x[j++];
    for(ll i=1;i<=cnt;i++) x[i+la-1]=a[i];
    return;
}
void merge(ll l,ll r){
    if(l>=r) return;
    ll mid=l+r>>1;
    merge(l,mid);
    merge(mid+1,r);
    mergesort(l,mid,mid+1,r);
    return;
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&x[i]);
    merge(1,n);
    cout<<ans;
    return 0;
}

等一发离散化+树状数组或权值线段树