信息学奥赛一本通：1311：【例2.5】求逆序对
|
逆序对
设 A 为一个有 n 个数字的有序集（n > 1），其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。例如，数组（3，1，4，5，2）的逆序对有(3, 1)，(3, 2)，(4, 2)，(5, 2)，共 4 个逆序对。
算法思路
求数组的逆序对就是对数组进行排序，在排序过程中记录逆序的数量即可。这样我们需要使用稳定排序算法，比如冒泡排序、插入排序和归并排序。数据范围分析
1、从题目中，我们可以知道 n 的范围是 [1, 10^5]，这样我们就知道所有 O(n^2) 复杂度的排序算法肯定是 TLE，也就是说冒泡排序和插入排序不能使用，只有是要归并排序。2、假设最坏的情况，也就是这 10^5 个数据全部是倒序，那么逆序对应该是 。这个数据什么意思？我们来回忆一下 C++ 数据类型 unsigned int 的最大范围是 4,294,967,295，也就是 ，说明 unsigned int 已经容纳不下这个数据。太太太坑爹了。
归并排序求逆序对
这个部分是分析的核心。首先我们用一个样例数据来说明，使用归并排序。假设我们有一个数列 [5 4 2 6 3 1]，使用归并排序来看一下有几个逆序对。第一步：二分，如下图所示。逆序对数量 = 0。
第二步：第四层 5 和 4 合并：i=l=1; r=2; mid=(l+r)/2=1; j=mid+1=2; 因为 5>4，逆序对数量+mid-i+1=1。b数组：[4 5 0 0 0 0]，j+1>r；退出；a 数组 [4 5 2 6 3 1]。
第三步：第四层 6 和 3 合并：i=l=4; r=5; mid=(l+r)/2=4; j=mid+1=5; 因为 6>3，逆序对数量+mid-i+1=2。b数组：[4 5 0 3 6 0]，j+1>r；退出；a 数组 [4 5 2 6 3 1]。
第四步：第三层 4,5 和 2 合并：i=l=1; r=3; mid=(l+r)/2=2; j=mid+1=3; 因为 4>2，逆序对数量+mid-i+1=4。b数组：[2 4 5 3 6 0]，j+1>r；退出；a 数组 [2 4 5 3 6 1]。
第五步：第三层 3,6 和 1 合并：i=l=4; r=6; mid=(l+r)/2=5; j=mid+1=6; 因为 3>1，逆序对数量+mid-i+1=6。b数组：[2 4 5 1 3 6]，j+1>r；退出；a 数组 [2 4 5 1 3 6]。
第六步：第二层 2,4,5 和 1,3,6 合并：i=l=1; r=6; mid=(l+r)/2=3; j=mid+1=4; 因为 2>1，逆序对数量+mid-i+1=9。b数组：[1 2 4 5 3 6]，j+1；对应 2<3，b数组：[1 2 4 5 3 6]，i+1；对应 4>3，逆序对数量+mid-i+1=11，b数组：[1 2 3 4 5 6]。j+1；对应 4<6，b数组：[1 2 3 4 5 6]；i+1，5<6，b数组：[1 2 3 4 5 6]；i+1>mid，退出，a 数组 [1 2 3 4 5 6]，有序。
从上面的分析可以看出，使用归并排序求逆序对，最核心的是下面这句话
ans+=mid-i+1;
【参考程序一】
#include<bits/stdc++.h>
using namespace std;
long long a[100001],r[100001];
long long n,ans;
void asort(long long begin,long long end)
{
if(begin==end)
return;
long long mid=(begin+end)/2;
asort(begin,mid);
asort(mid+1,end);
long long x=mid+1,y=begin,z=begin;
while(x<=end&&y<=mid)
if(a[x]<a[y])
{
ans+=mid-y+1;
r[z++]=a[x++];
}
else
r[z++]=a[y++];
while(x<=end)
r[z++]=a[x++];
while(y<=mid)
r[z++]=a[y++];
for(long long i=begin;i<=end;i++)
a[i]=r[i];
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++)
cin>>a[i];
asort(1,n);
cout<<ans;
return 0;
}