题目链接:http://www.jxsfczx.cn:888/problem/35
时间：1 秒 空间：512 MB

题目描述

给定一个序列a1,a2,…,an，如果存在 i < j 并且ai > aj，那么我们称之为逆序对，求逆序对的数目。
数据范围：N<=10^5。Ai<=10^5。时间限制为1s。

输入描述

第一行为n,表示序列长度，接下来的n个数表示序列中的第i个数。

输出描述

所有逆序对总数.

输入

4
3 2 3 2

输出

3

解题思路

求逆序数可以通过管理两个指针，两次扫描数组，暴力法求出，显然时间复杂度是O(n^2).那么有更快的办法吗？答案是肯定的。我们可以利用归并排序法，稍做改进即可．

算法:归并排序是分治法(分而治之)的一种典型应用，应用递归的思想，自顶向下思考：先假定MergeSort()可以将一个乱序的数组排好序，因此就可以开始"分"(将一个数组平均分成两部分)，再"治"(分别对前后部分调用MergeSort()使它们有序),最后再写一个合并子函数Merge(),它可以将两个有序的数组合并,Merge()实现起来比较容易．只需要管理两个指针，分别指向两个子数组的开头，开辟新内存保存中间结果，遍历完两个数组就可以完成，时间复杂度是O(n).

求逆序数对时，在Merge()中，合并两个已经有序的数组A、B.因为A、B有序,所以A,B各自的逆序数是0,故A、B的逆序数等于A,B之间的逆序数.

#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
void Merge(int A[], int L, int Mid, int R) {
    int *Temp = (int *)malloc((R - L + 1) * sizeof(int));
    int p = L, q = Mid, k = 0;
    while (p <= Mid - 1 && q <= R) {
        if (A[p] <= A[q])
            Temp[k++] = A[p++];
        else {
            Temp[k++] = A[q++];
            ans += Mid - p;//只是比归并排序多了这个.右边小,则左边剩下的都是这个数的逆序对
        }
    }
    while (p <= Mid - 1)
        Temp[k++] = A[p++];
    while (q <= R)
        Temp[k++] = A[q++];
    for (int i = 0; i < k; i++)
        A[i + L] = Temp[i];
}
void MSort(int A[], int L, int RightEnd) {
    if (L < RightEnd) {
        int mid = (L + RightEnd) / 2;
        MSort(A, L, mid);
        MSort(A, mid + 1, RightEnd);
        Merge(A, L, mid + 1, RightEnd);
    }
}
int main() {
    int n, A[100005];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    MSort(A, 0, n - 1);
    cout << ans << endl;
    return 0;
}