POJ 2299

//结果需要long long

#include

int milk[500001];
int temp[500001];
int cowNum;
long long res;

void mergesort(int *a,int start,int end);
void mymerge(int *a,int start,int mid,int end);
int mymax(int a,int b)
{
 return (a>b?a:b);
}

int main()
{
 int n,i;
 while(scanf("%d",&n)&&n!=0)
 {
  for(i=0;i  {
   scanf("%d",&milk[i]);
  }
  res=0;
  mergesort(milk,0,n-1);
  printf("%lld\n",res);
 }
 return 0;
}

void mergesort(int *a,int start,int end)
{
 if(end==start)
  return;
 int mid=(start+end)/2;
 mergesort(a,start,mid);
 mergesort(a,mid+1,end);
 mymerge(a,start,mid,end);
}
void mymerge(int *a,int start,int mid,int end)
{
 int i,length,leftpos,rightpos,count;
 length=mymax(mid-start+1,end-mid);

 leftpos=count=start;
 rightpos=mid+1;
 while(leftpos<=mid&&rightpos<=end)
 {
  if(a[leftpos]  {
   temp[count++]=a[leftpos++];
  }
  else
  {
   temp[count++]=a[rightpos++];
   res+=mid-leftpos+1;
  }
 }
 if(leftpos>mid)
 {
  while(rightpos<=end)
  {
   temp[count++]=a[rightpos++];
  }
 }
 if(rightpos>end)
 {
  while(leftpos<=mid)
  {
   temp[count++]=a[leftpos++];
  }
 }

 for(i=start;i<=end;i++)
 {
  a[i]=temp[i];
 }
}