题解 | #逆序数#

思路

先看一眼数据范围，1e5逐个数逆序数是肯定会超时的；
对于排序后的数组，每一个数前面序号比它大的数的个数就是它的逆序数，
因此我们可以想到一种O(nlogn)排序并求逆序数的方法，只需要套一个归并排序的板子，
然后统计归并排序时每个区域交换元素时相隔的元素个数就好了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,a[maxn],tmp[maxn];
long long cnt=0;

void Merge(int l,int m,int r){
    int i=l,j=m+1,k=l;
    while(i<=m&&j<=r){
        if(a[i]>a[j]){
            cnt+=j-k;
            tmp[k++]=a[j++];
        }else{
            tmp[k++]=a[i++];
        }
    }
    while(i<=m)    tmp[k++]=a[i++];
    while(j<=r)    tmp[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=tmp[i];
}

void MergeSort(int l,int r){
    if(l<r){
        int mid=l+r>>1;
        MergeSort(l,mid);
        MergeSort(mid+1,r);
        Merge(l,mid,r);
    }
    return;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    cnt=0;
    MergeSort(1,n);
    cout<<cnt<<endl;
    return 0;
}