POJ 2299 Ultra-QuickSort ---归并排序 求逆序

归并排序 的模板。

能求逆序。。。。

#include<stdio.h>
#include<string.h>

int n;
long long a[500005],b[500005];
long long sum;

void merge(int l,int m,int r)
{
	int i=l,j=m+1,k=0;
	while(i<=m && j<=r)
	{
		if(a[i]<=a[j])
			b[k++]=a[i++];
		else{
			b[k++]=a[j++];
			sum+=m-i+1;//这个就能求逆序了。。自己理解一下。。
		}
	}
	while(i<=m)
		b[k++]=a[i++];
	while(j<=r)
		b[k++]=a[j++];
	k=0;
	for(i=l;i<=r;i++)
		a[i]=b[k++];
}
void mergesort(int a,int b)
{
	if(a==b) return ;
	int m=(a+b)/2;
	mergesort(a,m);
	mergesort(m+1,b);
	merge(a,m,b);
}
int main()
{
	int i,j,k;
	while(scanf("%d",&n),n){
		for(i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		sum=0;
		mergesort(1,n);
		printf("%lld\n",sum);
	}
}