记录编号	161655	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2015-05-08 06:10:23	内存使用	1.05 MiB

#include <cstdio>
#include <algorithm>

using namespace std;

struct order{
	int data,ord;
};

bool comp(order a,order b)
{
	if(a.data==b.data) return a.ord<b.ord;
	return a.data<b.data;
}

order st[50003];

int n,tree[50003],status[50003],ans;

void update(int pos)
{
	while(pos<=n)
	{
		tree[pos]++;
		pos+=pos&(-pos);
	}
	return;
}

int SUM(int pos)
{
	int Sum=0;
	while(pos>0)
	{
		Sum+=tree[pos];
		pos-=pos&(-pos);
	}
	return Sum;
}

int main()
{
	freopen("px.in","r",stdin);
	freopen("px.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&st[i].data);
		st[i].ord=i;
	}
	sort(st+1,st+n+1,comp);
	for(int i=1;i<=n;i++)
		status[st[i].ord]=i;
	for(int i=1;i<=n;i++)
	{
		update(status[i]);
		ans+=i-SUM(status[i]);
	}
	printf("%d",ans);
	return 0;
}