记录编号	405857	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.285 s
提交时间	2017-05-17 15:55:07	内存使用	0.70 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MAXN = 5e4 + 10;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct NODE{ 
	int sum;
	NODE *ls, *rs;

	NODE(){ 
		ls = rs = NULL;
		sum = 0;
	}
};

inline int search(int *s, int k);
NODE* build(int l, int r);
void update(NODE *now, int k, int l, int r);
int query(NODE *now, int l, int r, int L, int R);

int N, n = 1;
int a[MAXN], oa[MAXN];
NODE *root;
LL ans;

int main(){ 
#ifndef LOCAL
	freopen("px.in", "r", stdin);
	freopen("px.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in();

	for(int i = 1; i <= N; ++i) a[i] = oa[i] = in();

	sort(oa + 1, oa + 1 + N);

	for(int i = 2; i <= N; ++i) if(oa[i] ^ oa[i - 1]) oa[++n] = oa[i];
	for(int i = 1; i <= N; ++i) a[i] = search(oa, a[i]);

	root = build(1, n + 1);
	update(root, a[1], 1, n + 1);
	for(int i = 2; i <= N; ++i){ 
		ans += query(root, a[i] + 1, n + 1, 1, n + 1);
		update(root, a[i], 1, n + 1);
	}

	printf("%lld", ans);
	return 0;
}

inline int search(int *s, int k){ 
	return lower_bound(s + 1, s + 1 + n, k) - s;
}

NODE* build(int l, int r){ 
	NODE *p = new NODE();

	if(l != r){ 
		int mid = (l + r) >> 1;
		p->ls = build(l, mid);
		p->rs = build(mid + 1, r);
	}

	return p;
}

void update(NODE *now, int k, int l, int r){ 
	if(l ^ r){ 
		int mid = (l + r) >> 1;

		if(k <= mid) update(now->ls, k, l, mid);
		else update(now->rs, k, mid + 1, r);
	}

	++now->sum;
	return ;
}

int query(NODE *now, int l, int r, int L, int R){ 
	if(l == L && r == R) return now->sum;

	int mid = (L + R) >> 1;
	if(r <= mid) return query(now->ls, l, r, L, mid);
	if(mid < l) return query(now->rs, l, r, mid + 1, R);

	return query(now->ls, l, mid, L, mid) + query(now->rs, mid + 1, r, mid + 1, R);
}