> #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;
> 	}
> }

• Re:顶！ (0) bbbbcccc 2018-12-09 22:26:51