//--------------2299 Ultra QuickSort
#include<stdio.h>
#define MAX 500001
_int64 MergeSort(long a[],long c[],int left,int right)
{
	int i,j,mid,temp,count;
	_int64 total;
	total=0;
	if (right>=left+1) {
		mid=(left+right)/2;
		total+=MergeSort(a,c,left,mid);
		total+=MergeSort(a,c,mid+1,right);
		count=0;
		for (i=left,j=mid+1;i<=mid && j<=right;)
		{
			if (a[i]>a[j]) {
				total+=mid-i+1;
				count++;
				c[count]=a[j];
				j++;
			} 
			else {
				count++;
				c[count]=a[i];
				i++;
			}
		}
		while (i<=mid) {
			count++;
			c[count]=a[i];
			i++;
		}
		while (j<=right) {
			count++;
			c[count]=a[j];
			j++;
		}
		for (i=left;i<=right;i++)
			a[i]=c[i-left+1];
	}
	return total;
}
	
int main(void)
{
	long a[MAX],c[MAX];
	int n,i,j;
	_int64 total;
	scanf("%d",&n);
	while (n!=0)
	{
		for (i=1;i<=n;i++)
			scanf("%ld",&a[i]);
		total=MergeSort(a,c,1,n);
		printf("%d\n",total);
/*		for (i=1;i<=n;i++) printf("%d ",a[i]);
		printf("\n"); */
		scanf("%I64d",&n);
		
	}
}

• 归并排序 逆序数 第2 版 (1298) ecjtubaowp 2007-02-27 16:51:28
  • 谢大牛！我看看我的问题在哪儿。 (0) testdirk 2007-02-27 17:54:03
    • 又仔细看了下发现我的问题太幼稚了，我输出的时候用的"%d"，应该是"%64Id"，我把这个给弄到输入离去了，就错了。AC了，顶一下！再次谢楼上的大牛！ (0) testdirk 2007-02-27 18:00:47
      • 在这也提醒下后来人，用_int64的时候不能用GCC编译，会CE，具体为什么不知，需要用C编译器就Okla. (0) Nowitzki 2007-02-27 18:03:23
  • 非常感谢！ (0) zouwq0209 2008-07-09 15:01:26
  • Re:归并排序 逆序数 第2 版 (1398) 6736881 2009-11-13 23:37:33