记录编号	229563	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	0.196 s
提交时间	2016-02-20 11:59:21	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct Node{
	int data,num;
}a[50001],c[50001];
void Divi(int,int);
void Merge(int,int,int);
int ans=0,n;
int main(){
	freopen("px.in","r",stdin);
	freopen("px.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].data);
		a[i].num=i;
	}
	Divi(1,n);
	printf("%d\n",ans);
	return 0;
}
void Divi(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	Divi(l,mid);Divi(mid+1,r);
	Merge(l,mid,r);
}
void Merge(int l,int mid,int r){
	int i=l,j=mid+1,k=l;
	while(k<=r){
		if(i>mid){
			c[k]=a[j];j++;k++;continue;
		}
		if(a[j].data<a[i].data&&j<=r){
			c[k]=a[j];j++;k++;ans+=mid-i+1;continue;
		}
		c[k]=a[i];i++;k++;
	}
	for(int i=l;i<=r;i++){
		a[i]=c[i];
	}
}