UVA 10810 - Ultra-QuickSort（歸並排序）

/*

 這個題用循環爆的話會TLE  所以有兩種方法 1、歸並排序 2、樹狀數組

 本題給出的是歸並排序的方法  歸並排序： 以分治為主要思想 不斷二分， 兩個相鄰的 數組進行歸並

 得出最小步數。

*/

#include<cstdio>

#include<cstring>

long long a[500010],b[500010],num;

long long merge_sort(long long *A,int x,int y,long long *T)
{
    if(y-x>1)
    {
        int m = (x+y)/2;
        int p = x,q = m,i = x;
        merge_sort(A,x,m,T);
        merge_sort(A,m,y,T);
        int ps=x;
        while(p<m||q<y)
        {

            if(q>=y||(p<m&&A[p]<=A[q]))
                T[i++] = A[p++],ps++;
            else
            {
                num+=m-p;
                //printf("%d.%d.%d.\n",num,A[p],A[q]);
                T[i++] = A[q++];
            }
        }
        for(int i = x; i < y; i++)
            A[i] = T[i];
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i = 0; i < n; i++)
            scanf("%lld",&a[i]);
        num=0;
        memset(b,0,sizeof(b));
        merge_sort(a,0,n,b);
        printf("%lld\n",num);
    }
    return 0;
}