#include<stdio.h>
#include<string.h>
int a[500005],t[500005];
__int64 merge_sort(int l,int r,int len)
{
	int i,temp,j;
	__int64 ans=0;
	if(len==0)
		return 0;
	temp=(l+r)/2;
	ans+=merge_sort(l,temp,temp-l);
	ans+=merge_sort(temp+1,r,r-temp-1);
	int p=l,q=temp+1;
	j=l;
	for(i=0;i<=len;i++)
	{
		if(q>r||(p<=temp&&a[p]<a[q]))
			t[j++]=a[p++];
		else
		{
			ans+=temp-p+1;
			t[j++]=a[q++];
		}
	}
	for(;l<=r;l++)
		a[l]=t[l];
	return ans;
}
inline void scan(int &n)
{
	char c;
	//while(c=getchar(),c<'0'||c>'9');
	n=0;
	while(c=getchar(),c<='9'&&c>='0')
		n=n*10+c-'0';
}
int main()
{
	int n,i;
	__int64 ans;
	while(scanf("%d",&n),n)
	{
		getchar();
		for(i=0;i<n;i++)
			scan(a[i]);
		ans=merge_sort(0,n-1,n-1);
		printf("%I64d\n",ans);
	}
}

• 仰慕下，我用的算导上的归并。。 (0) zxy_snow 2011-03-17 21:20:07
  • Re:仰慕下，我用的算导上的归并。。 (18) a19870209a 2012-02-23 10:42:13
• Re:merge144MS，不幸排在第一 (937) dahai1990 2011-07-05 18:46:23
  • Re:merge144MS，不幸排在第一 (57) l2ice 2011-08-30 12:35:47
• Re:merge144MS，不幸排在第一 (890) froest 2012-02-05 16:29:12
  • Re:merge144MS，不幸排在第一 (38) froest 2012-02-05 16:30:34
  • Re:merge144MS，不幸排在第一 (46) froest 2012-02-05 16:32:06