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

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

const int MAXN = 1e4 + 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;
	}
};

int search(double *s, double 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);

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

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

	for(int i = 1; i <= N; ++i){ 
		scanf("%lf", ooa + i);
		oa[i] = ooa[i];
	}

	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, ooa[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);
	}

	printf("%d", ans);

	return 0;
}

int search(double *s, double 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);
		if(mid < k) 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);
}