记录编号	128581	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2014-10-17 21:20:39	内存使用	1.15 MiB

#include<cstdio>
#include<ctime>
#include<cstring>
#define M 50001

int n;
int a[M],c[M];
long long min1[M],min2[M];
long long ans1=0,ans2=0;

void init();
void work();
void outit();
int lowbit(int x){return x&(-x);}
void add(int x,int num)
{
	while(x<=M)
	{
		c[x]+=num;
		x+=lowbit(x);
	}
}
int sum(int x)
{
	int tot=0;
	while(x>0)
	{
		tot+=c[x];
		x-=lowbit(x);
	}
	return tot;
}

int main()
{
	freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	//ios::sync_with_stdio(false);
	init();
	work();
	outit();
	return 0;
}
void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]++;
	}
	
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		min1[i]=sum(a[i]-1);
		add(a[i],1);
	}
	memset(c,0,sizeof(c));
	for(int i=n;i>=1;i--)
	{
		min2[i]=sum(a[i]-1);
		add(a[i],1);
	}
	for(int i=1;i<=n;i++)
	{
		//ans1+=max1[i]*max2[i];
		ans2+=min1[i]*min2[i];
	}
}
void outit()
{
	printf("%lld\n",ans2);
	//printf("%llf",double(clock())/CLOCKS_PER_SEC);
}