记录编号	438664	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	实力演员阵容	是否通过	通过
代码语言	C++	运行时间	0.111 s
提交时间	2017-08-16 21:53:34	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<time.h>
#include<cstdlib>
using namespace std;
int a[50010]={0},b[50010]={0};
int sum=0;
void merge_sort(int x,int mid,int y){
	int l=x,i=x,r=mid+1;
	for(;i<=mid&&r<=y;){
		if(a[i]>a[r]){
			b[l++]=a[i++];
			sum+=y-r+1;
		}
		else
			b[l++]=a[r++];
	}
	for(;i<=mid;)
		b[l++]=a[i++];
	for(;r<=y;)
		b[l++]=a[r++];
	for(int k=x;k<=y;k++)
		a[k]=b[k];
}
void merge(int x,int y){
	int mid=(x+y)/2;
	if(x!=y){
		merge(x,mid);
		merge(mid+1,y);
	}
	merge_sort(x,mid,y);
}
int main(){
	freopen("px.in","r",stdin);
	freopen("px.out","w",stdout);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	merge(0,n-1);
	cout<<sum;
	return 0;
}
/*
int main(){
	freopen("px.in","w",stdout);
	srand((int)time(NULL));
	cout<<50000<<endl;
	for(int i=0;i<50000;i++){
		cout<<rand()%1000000<<" ";
	}
}
*/