通過“歸併排序”尋找逆序對

題目描述

给出一个整数数列A,输出这个数列中的逆序对数量
逆序对定义：
Ai<Aj 而且 i>j
输入格式
第一行一个整数n
下面有n行，每行一个正整数
输出格式
一个整数，逆序对数目
数据规模：
n=50000
数列中的数小于1000000

【分析】
雖然題目很簡單，但是數據量很大，所以直接暴力搜索肯定會超時。本題可以用歸併排序（Merge Sort）來快速完成。
【正確代碼】

C++语言: Codee#24223

//通過歸併排序尋找逆序對
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define MAX 500005
int n,t[MAX],a[MAX];
long long sum;
void merge(int l, int mid, int r )
{
    int p = 0;
    int i = l, j = mid + 1;
    while(i <= mid&& j <= r)
    {
        if(a[i] > a[j])
        {
            t[p++] = a[j++];
            sum =sum + mid - i + 1;
        }
        else
        {
            t[p++] = a[i++];
        }
    }
    while(i <= mid) t[p++] = a[i++];
    while(j <= r) t[p++] = a[j++];
    for(i = 0; i < p; i++)
    {
        a[l + i] = t[i];
    }
}
void mergesort(int l ,int r)
{
    if(l < r)
    {
        int mid = (r - l) / 2 + l;
        mergesort(l , mid);
        mergesort(mid + 1 , r);
        merge(l, mid , r);
    }
}

int main()
{
    freopen("px.in","r",stdin);
    freopen("px.out","w",stdout);

    scanf("%d\n",&n);
    sum=0;
    for(int i = 0; i < n; i++)
    {
        scanf(" %d ", &a[i]);
    }
    mergesort(0 , n - 1);
    printf("%lld\n", sum);

    return 0;
}