记录编号	41641	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]最接近神的人	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.675 s
提交时间	2012-08-06 17:44:35	内存使用	4.10 MiB

#include <cstdio>
const int N = 500000 + 10;
int n, a[N], b[N];
unsigned long long s;
void Merge(int l, int r) {
    if(l >= r) return;
    int m = (l + r) / 2;
    Merge(l, m); Merge(m+1, r);
    int i = l, j = m + 1, k = l;
    do {
        if(a[i] > a[j]) {
            s += m - i + 1;
            b[k++] = a[j++];
        } else
            b[k++] = a[i++];
    } while(i <= m && j <= r);
    while(i <= m) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(int i=l; i<=r; i++) a[i] = b[i];
}
int main() {
    freopen("sop.in", "r", stdin);
    freopen("sop.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    Merge(1, n);
    printf("%lld\n", s);
    return 0;
}