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;
}
}