记录编号	229470	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.142 s
提交时间	2016-02-20 10:53:29	内存使用	0.67 MiB

#include<cstdio>
#include<cstring>
int data[50005];
int buf[50005];
int tot=0;
void divide(int l,int r){
	if(l+1>=r)return;
	int mid=(l+r)>>1;
	divide(l,mid);
	divide(mid,r);
	int j=l,k=mid,len=0;
	while(j<mid&&k<r){
		if(data[j]<=data[k]){
			buf[len]=data[j];j++;
		}else{
			buf[len]=data[k];k++;
			tot+=(mid-j);	
		}
		len++;
	}
	if(j==mid&&k==r)return;
	else if(j!=mid){
		while(j<mid){
			buf[len]=data[j];
			len++;j++;
		}
	}
	else while(k<r){
		buf[len]=data[k];
		len++;k++;
	}
	memcpy(data+l,buf,len<<2);
}
int read(){
	char ch;int x;
	while(ch=getchar(),ch>'9'||ch<'0');
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
	return x;
}
int main(){
	freopen("px.in","r",stdin);
	freopen("px.out","w",stdout);
	int n;n=read();
	for(int i=0;i<n;++i)data[i]=read();
	divide(0,n);
	printf("%d",tot);//while(1);
	fclose(stdin);fclose(stdout);
	return 0;
}