记录编号	128643	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2014-10-18 06:36:35	内存使用	1.25 MiB

#include<cstdio>
#include<algorithm>
#define Lowbit(x) x & (-x)
using namespace std;
struct dx
{
	int num;
	int i,k,s;
};
dx a[50001];
int n;
int c[50001];
long long Ans;
void add(int k,int x)
{
	while(k<=n)
	{
		c[k]+=x;
		k+=Lowbit(k);
	}
}
int PR(int x)
{
	int sum=0;
	while(x)
	{
		sum+=c[x];
		x-=Lowbit(x);
	}
	return sum;
}
bool comp1(dx a,dx b)
{
	if(a.num==b.num) return a.i>b.i;
	return a.num<b.num;
}
bool comp2(dx a,dx b){return a.i<b.i;}
int main()
{
	freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].num++,a[i].i=i;
	sort(a+1,a+n+1,comp1);
	for(int i=1;i<=n;i++)
	{
		a[i].k=i;
		if(a[i].num!=a[i-1].num) a[i].s=i-1;
		else a[i].s=a[i-1].s;
	}
	sort(a+1,a+n+1,comp2);
	for(int i=1;i<=n;i++)
	{
		int sum=PR(a[i].k-1);
		if(a[i].s>sum) Ans+=sum*(a[i].s-sum);
		add(a[i].k,1);
	}
	printf("%lld",Ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}