#include<iostream>
using namespace std;
#define N 500000
long long x,a[2][N];
void merge(long long *sr,long long *tr,int i,int m,int n)
{
	int j=m+1,k=i;
	for(;i<=m&&j<=n;++k)
	{
		if(sr[i]<=sr[j])tr[k]=sr[i++];
		else x+=j-k,tr[k]=sr[j++];
	}
	if(i<=m)for(;k<=n;)tr[k++]=sr[i++];
	if(j<=n)for(;k<=n;)tr[k++]=sr[j++];
}
int main()
{
	int n;
	cin>>n;;
	while(n)
	{
		x=0;
		for(int i=0;i<n;i++)cin>>a[0][i];
		int k=0;
		for(int i=1;i<n;i*=2)
		{
			for(int j=0;j+i<n;j+=2*i)
			merge(a[k],a[(k+1)%2],j,j+i-1,(j+2*i-1)<(n-1)?(j+2*i-1):(n-1));
			k=(k+1)%2;
		}
		cout<<x<<endl;
		cin>>n;
	}
}

• 顶！ (694) shenfangyi 2006-11-09 12:09:13
  • Re:顶！ (0) bbbbcccc 2018-12-09 22:26:51