POJ 2299

http://poj.org/problem?id=2299

劉汝佳經典歸并排序求逆序：

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500005
long long cnt=;
long long a[maxn],T[maxn];
void merge_sort(long long *A,long long x,long long y,long long *T)
{
    if(y-x>)
    {
       long long m=x+(y-x)/;
       long long 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++];
            cnt += m-p;
           }
       }
       for(i=x;i<y;++i) A[i]=T[i];
    }
}

int main()
{
    long long n;

    while(cin>>n&&n)
    {
        for(long long i=;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        cnt=;
        merge_sort(a,,n,T);
        cout<<cnt<<endl;
    }
}