The Number of Inversions(逆序数与归并排序)

For a given sequence A = a 0 , a 1 , ⋅ ⋅ ⋅ a n − 1 A = {a_0,a_1,···a_{n-1}} A=a0​,a1​,⋅⋅⋅an−1​,the number of pairs ( i , j ) (i,j) (i,j) where a j a_j aj​ and i < j i 我知道你们不想看英文题面，所以以下内容我直接翻译好了

bubbleSort(A)
  cnt = 0 // the number of inversions
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

  return cnt

对于给定的序列 A A A,打印出 A A A的逆序数。注意你不应该使用上述程序，这会导致TLE。

第一行为一个正整数 n n n，为 A A A的元素个数，第二行为 n n n个元素 a i （ i = 0 , 1 , ⋅ ⋅ ⋅ n − 1 ） a_i（i = 0,1,···n-1） ai​（i=0,1,⋅⋅⋅n−1）

输出逆序数

5
3 5 2 1 4

6

比如说给一个序列 5 , 4 , 3 , 2 , 1 {5,4,3,2,1} 5,4,3,2,1，在5后面有4个数比他小，在4后有三个比他小···所以这个序列的逆序数为4+3+2+1 = 10。也就是计算排在这个数之后比其大的数的个数。我们可以直接冒泡排序，因为冒泡排序就是不断比较相邻两个数大小，但 O ( n 2 ) O(n^{2}) O(n2)复杂度会超时。这里使用归并排序的思想，因为在最后归并的时候，会比较两个数组里数的大小。
首先我们要清楚我们应该在归并的代码里增加记录逆序数的代码。我默认是有两个数组 L 1 , L 2 L1,L2 L1,L2且 L 2 L2 L2的数相对于 L 1 L1 L1更靠后。所以如果 L 2 L2 L2中有数比 L 1 L1 L1中的数小，那么就可以记录了。上述过程在哪里判断呢？就是在 L 1 , L 2 L1,L2 L1,L2逐个判断将较小值赋给原数组的过程中。

while (i < l1 && j < l2)
    {
        if (L1[i] <= L2[j])
        {
            A[k] = L1[i];
            i++;
            k++;
        }
        else
        {
            A[k] = L2[j];
            j++;
            k++;
            sum += l1 - i;//这里就是记录逆序数值
        }
    }

如果 L 2 [ j ] L2[j] L2[j]小于 L 1 [ i ] L1[i] L1[i]，而 L 1 [ k ] ( k > i ) L1[k](k>i) L1[k](k>i)都大于 L 1 [ i ] L1[i] L1[i]也就都大于 L 2 [ j ] L2[j] L2[j]。因此要加的逆序数就是此时 L 1 L1 L1中k的数量。这里我用 L 1 L1 L1的长度减去i得到 L 1 L1 L1中大于 L 1 [ i ] L1[i] L1[i]的个数。

我之前每次写归并排序的时候，总是被判断时是 ＞ ＞ ＞还是 ≥ ≥ ≥给搞晕，还有最后归并的时候长度到底左边+1还是右边+1搞懵。
所以在这里我记录一下我自己的想法

	int l1 = mid - left + 1;
	int l2 = right - mid;
	int *L1 = new int[l1];
	int *L2 = new int[l2];
	for (int i = 0; i < l1; i++)
	{
	    L1[i] = A[i + left];
	}
	for (int i = 0; i < l2; i++)
	{
	    L2[i] = A[i + mid + 1];
	}

这里左边长度是 m i d − l e f t + 1 mid - left +1 mid−left+1，右边长度是 r i g h t − m i d right - mid right−mid。假设我们现在 l e f t = 0 ， m i d = 1 ， r i g h t = 2 left=0，mid=1，right=2 left=0，mid=1，right=2，那么左边长度为1，右边长度为1，符合归并排序的规定。如果左边为 m i d − l e f t mid-left mid−left，右边为 r i g h t − m i d + 1 right-mid+1 right−mid+1，那么左边长度变为0，右边长度为2，右边有两个元素没能进行比较就加入了新数组里，这样归并的划分并不充分。原因在于我们取mid的时候是向下取整，这就导致 r i g h t − m i d right-mid right−mid的值回避 m i d − l e f t mid-left mid−left大一些。

#include 
using namespace std;
long long sum = 0;
void merge(int A[], int left, int mid, int right)
{
    int l1 = mid - left + 1;
    int l2 = right - mid;
    int *L1 = new int[l1];
    int *L2 = new int[l2];
    for (int i = 0; i < l1; i++)
    {
        L1[i] = A[i + left];
    }
    for (int i = 0; i < l2; i++)
    {
        L2[i] = A[i + mid + 1];
    }
    int i = 0, j = 0;
    int k = left;
    while (i < l1 && j < l2)
    {
        if (L1[i] <= L2[j])
        {
            A[k] = L1[i];
            i++;
            k++;
        }
        else
        {
            A[k] = L2[j];
            j++;
            k++;
            sum += l1 - i;
        }
    }
    while (i < l1)
    {
        A[k] = L1[i];
        i++;
        k++;
    }
    while (j < l2)
    {
        A[k] = L2[j];
        j++;
        k++;
    }
    // for (int k = left; k < right; k++)
    // {
    //     if (L1[i] <= L2[j])
    //     {
    //         A[k] = L1[i];
    //         i++;
    //     }
    //     else
    //     {
    //         A[k] = L2[j];
    //         j++;
    //     }
    // }
}
void mergeSort(int A[], int left, int right)
{
    if (right > left)
    {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid + 1, right);
        merge(A, left, mid, right);
    }
}
int main()
{
    int n;
    int *A;
    cin >> n;
    A = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    mergeSort(A, 0, n - 1);
    // for (int i = 0; i < n; i++)
    // {
    //     cout << A[i] << " ";
    // }
    // cout << endl;
    cout << sum << endl;
}

题目地址ALDS1_5_D