题目难度：三星
考察点：归并排序

方法：归并排序

1.分析：

这个题的本质其实就是求一个逆序数，那么如何求逆序数呢，我们可以采用归并排序的方法。
归并排序：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
具体操作：
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
举个例子:
6 2 7 5 3 1 4
第一步：(6,2) (7,5) (3,1) (4)
两两排序(2,6)(5,7)(1,3)(4)
第二步：{(2,6),(5,7)}{(1,3),(4)}
两两排序(2,5,6,7) (1,3,4)
第三步：{(2,5,6,7),(1,3,4)}
两两排序 1 2 3 4 5 6 7 完成真正的排序。
其实我们就是先用递归算法将这 n 个数分解成一个一个的数，因为这样是已经排好序的，然后我们在两两进行合并。

算法实现：
(1). 输入n和对应的n个数。
(2).采用归并排序进行求逆序数。
(3). 输出逆序数结果。

2.复杂度分析：

时间复杂度：O(n*log(n)) 
空间复杂度：O(n)

3.代码： 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4+5;
int cnt = 0;
int a[MAXN],p[MAXN];
void Merge_Array(int first, int mid, int last)
{
    int i=first, j=mid+1, k=first;
    while(i<=mid && j<=last)
    {
        if(a[i] <= a[j])
            p[k++] = a[i++];
        else
        {
            p[k++] = a[j++];
            cnt += j-k;
        }
    }
    while(i <= mid)
        p[k++] = a[i++];
    while(j <= last)
        p[k++] = a[j++];
    for(int i=first; i<=last; i++)
        a[i] = p[i];
}
void Merge_Sort(int first, int last)
{
    if(first < last)
    {
        int mid = (first + last) >> 1;
        Merge_Sort(first, mid);
        Merge_Sort(mid+1, last);
        Merge_Array(first, mid, last);
    }
}
int main() {
    int n; cin>>n;
    cnt = 0;
    for(int i=0; i<n; i++) cin>>a[i];
    Merge_Sort(0, n-1);
    cout<<cnt<<endl;
}