题解 UVA11858 【Frosh Week】

· · 题解

非常经典的求逆序对个数问题。

我们可以使用归并排序求逆序对。

首先来学一下归并排序。它首先把数组一分为二，分别进行归并排序，然后把两个排好序的数组合并成一个有序的大数组，最后合并出来的数组就是有序的。这样递归并一层一层向上合并的算法，其时间复杂度是 O(n\log n)。给一个代码实现：

int a[100010],tp[100010];
void mergesort(int l,int r){
    if(l>=r) return ;
    //将数组一分之二，分别进行归并排序：
    int mid=(l+r)>>1;
    mergesort(l,mid),mergesort(mid+1,r);
    //把两个排好序的数组合并成一个大数组：
    //具体实现方法是用一个数组 tp 存储合并出的数组，
    //最后把 tp 数组放回 a 数组。
    int i=l,j=mid+1,n1=mid,n2=r,cnt=l;
    while(i<=n1&&j<=n2){
        if(a[i]<=a[j]) tp[cnt++]=a[i++];
        else tp[cnt++]=a[j++];
    }
    //把剩余的元素放进去，两个 while 一定只能执行一个
    while(i<=n1) tp[cnt++]=a[i++];
    while(j<=n2) tp[cnt++]=a[j++];
    for(int k=l;k<=r;k++) a[k]=tp[k];
    return ;
}

那如何使用归并排序求逆序对个数呢？改一行代码就行了：

else ans+=n1-i+1,tp[cnt++]=a[j++];

为什么？

首先 i<j 且 a_i>a_j，这个没问题。

我们想一下， a_{l\cdots mid} 和 a_{mid+1\cdots r} 这两个小数组是有序的，对吧？

它们都是递增的，\forall i\in[l,mid-1] \; a_i 一定 <a_{i+1}，是吗？

那，当前这个 a_i 已经 >a_j 了，对于更大的 a_{i+1},a_{i+2},\cdots，它们也 >a_j 吗？

答案是肯定的。换一种说法，a_{i\cdots mid}>a_j，你看，这 mid-i+1 个逆序对不就出现了吗？

如果你还不明白，看 link。

了解这些后，代码就好写了。注意 \max ans=\frac{10^5\times (10^5-1)}{2} 会爆 int，开 long long。这里给出我的实现板子：

#include <iostream>
using namespace std;
typedef long long LL;
int t[1000010];
LL revp(int a[],int l,int r){
//Reverse Pair 逆序对
    if(l>=r) return 0;
    int mid=l+r>>1;
    LL ans=revp(a,l,mid)+revp(a,mid+1,r);
    int i=l,j=mid+1,n1=mid,n2=r,cnt=l;
    while(i<=n1&&j<=n2){
        if(a[i]<=a[j]) t[cnt++]=a[i++];
        else ans+=n1-i+1,t[cnt++]=a[j++];
    }
    while(i<=n1) t[cnt++]=a[i++];
    while(j<=n2) t[cnt++]=a[j++];
    for(int k=l;k<=r;k++) a[k]=t[k];
    return ans;
}
int n,a[1000010];
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>a[i];
        cout<<revp(a,1,n)<<endl;
    }
    return 0;
}

练习：