4754680_tle.cpp

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

#include<iostream>
using namespace std;
int q[500005];
int n;
int all;
void merge(int b,int mid,int e)
{
	int ll,rl,i,j,k;
	ll=mid-b+1;
	rl=e-mid;
	int l[500005];
	int r[500005];
	for(i=b,k=0;i<=mid;k++,i++)
		l[k]=q[i];
	for(i=mid+1,k=0;i<=e;k++,i++)
		r[k]=q[i];
	for(i=0,j=0,k=b;k<=e;k++)
	{
		if(i==ll)
		{
			q[k]=r[j++];
			all+=ll-i;
		}
		else
		if(j==rl) q[k]=l[i++];
		else
		if(l[i]<=r[j]) q[k]=l[i++];
		else
		{
			q[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,mid,e);
	}
}
int main()
{
	int i;
	while(1)
	{
	cin>>n;
	if(n==0) return 0;
	for(i=0;i<n;i++)cin>>q[i];
	all=0;
	mergesort(0,n-1);
	cout<<all<<endl;
	}
	return 0;
}