记录编号	353734	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2016-11-18 18:37:23	内存使用	0.71 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdarg>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
using namespace std;
int a[55555];
int t[55555];
long long ans;
void msort(int l, int m, int r)
{
    int i = l;
    int j = m+1;
    int k = l;
    while(i <= m && j <= r)
    {
        if(a[i] > a[j])
        {
            t[k++] = a[j++];
            ans += m-i+1; 
        }else
        {
            t[k++] = a[i++];
        }
    }
    while(i <= m)t[k++] = a[i++];
    while(j <= r)t[k++] = a[j++];
    for(int p = l; p <= r; p++)a[p] = t[p];
}
void gg(int l, int r)
{
    if(l < r)
    {
        int m = (l+r)>>1;
        gg(l, m);
        gg(m+1, r);
        msort(l, m, r);
    }
}
int main()
{
    freopen("px.in", "r", stdin);
    freopen("px.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d", a+i);
    gg(1, n);
    printf("%lld\n", ans);
    return 0;
}