luogu_1908 逆序对

#include <cstdio>
#include <iostream>
#include <cctype>
using namespace std;
const int N=40010;
int n,a[N],t[N];
long long ans;

inline int read(){
    char c; int x=0;
    c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}

inline void merge(int l,int r){
    if(l>=r)return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,head=l;
    while(i<=mid && j<=r){
        if(a[i]<=a[j])t[head++]=a[i++];
        else {t[head++]=a[j++]; ans=ans+mid-i+1;}
    }
    while(i<=mid)t[head++]=a[i++];
    while(j<=r)t[head++]=a[j++];
    for(register int k=l;k<=r;k++)a[k]=t[k];
}

int main(){    
    n=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    merge(1,n);
    //for(register int i=1;i<=n;i++)printf("%d ",a[i]);
    //puts("");
    printf("%d
",ans);
    return 0;
}