#include<iostream>
using namespace std;
#define MAXN 500000
int x[MAXN+1];
int z[MAXN+1];
__int64 reverse;
void merge(int low,int mid,int high)
{
int i=low,j=mid+1,q=0;
while (i<=mid && j<=high)
{
if (x[i]<=x[j])
z[q++]=x[i++];
else {
z[q++]=x[j++];
reverse+=mid-i+1;
}
}
while (i<=mid)
z[q++]=x[i++];
while (j<=high)
z[q++]=x[j++];
for(i=0;i<q;i++)
x[low+i]=z[i];
}
void mergesort(int low,int high)
{
int mid;
if ( low< high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
int main()
{
int n,i;
while(scanf("%d",&n)==1 && n!=0)
{
for(i=0;i<n;i++)
scanf("%d",&x[i]);
reverse=0;
mergesort(0,n-1);
printf("%I64d\n",reverse);
}
return 0;
}posted on 2009-07-12 14:59
wyiu 阅读(94)
评论(0) 编辑 收藏 引用 所属分类:
POJ