poj2299--归并排序求逆序数

/** \brief poj2299

 *

 * \param date 2014/8/5

 * \param state AC

 * \return memory 4640K time 3250ms

 *

 */

#include <iostream>

#include <fstream>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN=500000;

int Arr[MAXN];

int T[MAXN];

//__int64 t;

__int64 t;

void merge_sort(int* A,int x,int y,int* T)

{

    if(y-x>1)

    {

        int m=x+(y-x)/2;//partition

        int p=x,q=m,i=x;

        merge_sort(A,x,m,T);

        merge_sort(A,m,y,T);

        while(p<m || q<y)

        {

            if(q>=y || (p<m && A[p]<=A[q]))

                T[i++]=A[p++];//从左半数组拷贝到暂时空间

            else

            {

                T[i++]=A[q++];//从右半数组……

                t+=m-p;//统计逆序数对

            }

        }

        for(int i=x;i<y;i++)

            A[i]=T[i];//从辅助空间复制回A数组

    }

}

int main()

{

    //cout << "Hello world!" << endl;

    //freopen("input.txt","r",stdin);

    int n=0;

    while(scanf("%d",&n))

    {

        if(n==0)break;

        memset(Arr,0,sizeof(Arr));

        memset(T,0,sizeof(T));

        for(int i=0;i<n;i++)

            cin>>Arr[i];

        merge_sort(Arr,0,n,T);

        printf("%I64d",t);

        t=0;

        cout<<endl;

    }

    return 0;

}

用归并排序求序列的逆序数