题目
分析
这道题延续前一道题P1177：排序（模板），用归并排序的特性快速计算逆序对（Inversions）。
所谓逆序对，就是在一个数组中，存在\(i\lt j, a[i]\gt a[j]\)。显然，经过排序后，这两个数字一定会交换位置，所以称为“逆序对”。
观察归并排序的过程：
- \(A[i]\le A[j]\)，说明
A[i]在前，拿出A[i]给tmp[k]——这里的k指示tmp数组中下一个要处理的位置。A数组左边部分要看下一个（i++）。tmp数组的定位也要前进一次（k++）。 - \(A[i]\gt A[j]\)，说明
A[j]在前，拿出A[j]给tmp[k]——这里的k指示tmp数组中下一个要处理的位置。A数组右边部分要看下一个（i++）。tmp数组的定位也要前进一次（k++）。
其中的情况2表明A[j]要提前，它和A[i]构成了一个逆序对。而且，此时A[i]后面的数也一定比A[j]大，一共有mid-i+1个。所以一旦出现这个情况，逆序对数量就要增加mid-i+1个：
while (i <= mid && j <= r)
{
if (a[i] <= a[j])
{
tmp[k++] = a[i++];
}
else
{
// When we take element from right array, it forms inversions
// with all remaining elements in left array
inv_count += (mid - i + 1);
tmp[k++] = a[j++];
}
}特别注意：还需要递归加上左侧和右侧的逆序对数，再计算如上例中需要跨越边界的逆序对数。
答案
思考
用暴力算法当然可以，但时间复杂度是\(O(N^2)\)，而归并排序的时间复杂度只有\(O(n log n)\)，可以满足题目中要求\(1\le n\le 5×10^5\)的要求。