4754697_tle.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 52 行

#include<iostream>
using namespace std;
__int64 x[500005];
int all;
void merge(int b,int e,int mid)
{
	int ll=mid-b+1;
	int rl=e-mid;
	__int64 l[500005];
	__int64 r[500005];
	int i,j,k;
	for(i=0,k=b;k<=mid;i++,k++) l[i]=x[k];
	for(i=0,k=mid+1;k<=e;i++,k++) r[i]=x[k];
	for(k=b,i=0,j=0;k<=e;k++)
	{
		if(i==ll) x[k]=r[j++];
		else
			if(j==rl) x[k]=l[i++];
			else
				if(l[i]<=r[j]) x[k]=l[i++];
				else{
					x[k]=r[j++];all+=ll-i;
				}
	}
}
void mergesort(int b,int e)
{
	if(b>=e) return ;
	else
	{
		int mid=(b+e)/2;
		mergesort(b,mid);
		mergesort(mid+1,e);
		merge(b,e,mid);
	}
}
int main()
{
	int n;
	while(1)
	{
		scanf("%d",&n);
		if(n==0) return 0;
		int i;
		all=0;
		for(i=0;i<n;i++) scanf("%i64d",x+i);
		mergesort(0,n-1);
		cout<<all<<endl;
	}
	return 0;
}