记录编号	548945	评测结果	AAAAAAAAAA
题目名称	477.排序工作量-加强版	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	1.386 s
提交时间	2020-02-03 11:22:41	内存使用	13.85 MiB

#include<bits/stdc++.h>
using namespace std;
int a[50001];
int solve(int l,int r){
    int ans=0;
    if(l>=r) return 0;
    int m=(l+r)>>1;
    ans+=solve(l,m);     sort(a+l,a+m+1);
    ans+=solve(m+1,r);   sort(a+m+2,a+r+1);
    for(int i=m+1;i<=r;i++){
        if(a[m]<=a[i]) continue;
        ans+=m-(upper_bound(a+l,a+m,a[i])-(a+1));
    }
    return ans;
}
int main(){
    freopen("px.in","r",stdin);
    freopen("px.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	cin>>a[i]; 
	} 
    cout<<solve(1,n)<<endl;
    return 0;
}