NYOJ117 求逆序數

題目分析：
如果直接一個一個的找，時間復雜度是O(n^2)，這道題數據量很大，這樣肯定會超時的。我們肯定都之後把有序數組a和b歸並成另外一個有序數組。這個思想可以用到這裡來，假設需要歸並的數據段是[Begin,Mid)和[Mid,End)。用i，j分別遍歷兩個數據段，如果後面數據段中有數據比前一個數據段中的元素小，那麼它跨越的長度就是逆序對的個數，即Mid-i，i是第一個比j大的數。這裡要注意，數組最大的元素個數是10^6，最多的逆序對的個數為10^12-10^6，int最大也就2*10^9。肯定會越界的，所以這裡要用long long來計數。

[cpp]
include<stdio.h>  
#include<string.h>  
long long Merge(int *arr, int *ans, int Begin, int Mid, int End) 
{ 
    int i,j,k; 
    long long count = 0; 
    for(i = Begin, j = Mid, k = Begin; i < Mid && j < End; ++k) 
    { 
        if(arr[i] <= arr[j]) 
            ans[k] = arr[i++]; 
        else 
        { 
            //數組2中跨越數組1的長度即為逆序對的個數  
            count += Mid - i; 
            ans[k] = arr[j++]; 
        } 
    } 
    for( ; i < Mid; ++i, ++k) 
        ans[k] = arr[i]; 
    for( ; j < End; ++j, ++k) 
        ans[k] = arr[j]; 
    memcpy(&arr[Begin], &ans[Begin], (End - Begin) * sizeof(int)); 
    return count; 
} 
 
long long MergeSort(int *arr, int *ans, int nLen) 
{ 
    int i,l,e; 
    long long count = 0; 
    //步長跨度  
    for(l = 1; l < nLen; l *= 2) 
    { 
        for(i = 0; i + l < nLen; i += l + l) 
        { 
            //第二部分的結束  
            e = i + l + l > nLen ? nLen : i + l + l; 
            count += Merge(arr, ans, i, i + l, e); 
        } 
    } 
    return count; 
} 
 
int arr[1000001]; 
int ans[1000001]; 
int main() 
{ 
    int i,n,t; 
    long long count; 
    scanf("%d", &t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        for(i = 0; i < n; ++i) 
            scanf("%d", &arr[i]); 
        count = MergeSort(arr, ans, n); 
        printf("%lld\n", count); 
    } 
    return 0; 
}