[POJ2299]Ultra-QuickSort[逆序对,归并排序]

#include<cstdio>
#define in inline
#define re register
#define int long long
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    if(b) return -s;
    return s;
}
int n,a[510000],d[510000],ans;
void msort(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	re int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j]) d[k++]=a[i++];
		else d[k++]=a[j++],ans+=mid-i+1;
//左半区间和右半区间为两个子问题, 两个区间之内的逆序对已求出, 现在合并两区间, 只要考虑跨区间的逆序对
//当a[j]>a[i]时, a[i~mid]区间内每一个数与a[j]构成一个逆序对
	}
	while(i<=mid) d[k++]=a[i++];
	while(j<=r) d[k++]=a[j++];
	for(i=l;i<=r;++i) a[i]=d[i];
}				
signed main()
{
	while(1)
	{
		n=read();
		if(!n) break;
		for(re int i=1;i<=n;++i) a[i]=read();
		msort(1,n);
		printf("%lld\n",ans);
		ans=0;
	}
	return 0;
}