树状数组

void sol(){    for(int i=1;i<=n;++i) bs[i]=0;    for(int i=1;i<=n;++i)    scanf("%d",a+i),g[i]=a[i];    sort(g+1,g+1+n);    for(int i=1;i<=n;++i)        a[i]=n+1-(lower_bound(g+1,g+1+n,a[i])-g);    ll ans=0;    for(int i=1;i<=n;++i)    {        for(int j=a[i]-1;j>=1;j-=j&-j) ans+=bs[j];        for(int j=a[i];j<=n;j+=j&-j) ++bs[j];    }    printf("%lld\n",ans);}

归并

const int N = 1010;int a[N];int c[N];int cnt = 0;void MergeSort(int l, int r){    int mid, i, j, tmp;    if (r > l + 1)    {        mid = (l + r) / 2;        MergeSort(l, mid);        MergeSort(mid, r);        tmp = l;        for (i = l, j = mid; i < mid && j < r;)        {            if (a[i] > a[j])            {                c[tmp++] = a[j++];                cnt += mid - i;            }            else            {                c[tmp++] = a[i++];            }        }        if (j < r)        {            for (; j < r; ++j)            {                c[tmp++] = a[j];            }        }        else        {            for (; i < mid; ++i)            {                c[tmp++]=a[i];            }        }        for (i = l; i < r; ++i)        {            a[i] = c[i];        }    }    return ;}