学步园

题目分析：求逆序数，，，

思路：归并排序，关键在于统计逆序数，如果arr[i]>arr[j],则，ans+=m-i+1,

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
__int64 ans;
int arr[1001000],arr1[1001000];
void Merge(int s,int m,int t);
void MergeSort(int s,int t)
{
	if(s==t)
	{
		arr1[s]=arr[s];
	}
	else
	{
		int m=(s+t)/2;
		MergeSort(s,m);
		MergeSort(m+1,t);
        Merge(s,m,t);
	}
}
void Merge(int s,int m,int t)
{
   int i=s,j=m+1,k=s;
   while(i<=m&&j<=t)
   {
       if(arr[i]<=arr[j])
	   {
		   arr1[k++]=arr[i++];
	   }
	   else
	   {
           arr1[k++]=arr[j++];
		   ans+=m-i+1;//注意这，，，arr[i]>arr[j],则从arr[i]到arr[m]都是逆序数
	   }
   }
   if(i<=m)
	   while(i<=m)
	   {
		   arr1[k++]=arr[i++];
		   //ans++;
	   }
   else
	   while(j<=t)
		   arr1[k++]=arr[j++];
   for(int p=s;p<=t;p++)
	   arr[p]=arr1[p];
}
int main()
{
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&arr[i]);
		ans=0;
		MergeSort(1,n);

		/*for(int i=1;i<=n;i++)
			printf("%d   ",arr[i]);
		printf("\n");*/

		printf("%I64d\n",ans);
	}
	//system("pause");
	return 0;
}