记录编号	233177	评测结果	AAAAAAAAAA
题目名称	1260.三元数对	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2016-03-04 10:27:47	内存使用	0.86 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ori[30005];
int dict[30005];
int num[30005];
int c[30005];
int before[30005];
int lowbit(int x){
	return x&-x;
}
void update1(int x){
	for(int i=x;i<30005;i+=lowbit(i))c[i]++;
}
int sum1(int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i))ans+=c[i];
	return ans;
}
void update2(int x){
	for(int i=x;i;i-=lowbit(i))c[i]++;
}
int sum2(int x){
	int ans=0;
	for(int i=x;i<30005;i+=lowbit(i))ans+=c[i];
	return ans;
}
int read(){
	int x;char ch;
	while(ch=getchar(),ch>'9'||ch<'0');
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
bool cmp(const int &a,const int &b){
	return ori[a]<ori[b];
}
int main(){
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	int n=read();
	for(int i=1;i<=n;++i){
		num[i]=i;
		ori[i]=read();
	}
	sort(num,num+n+1,cmp);
	int cnt=3,old=-1;
	for(int i=1;i<=n;++i){
		if(ori[num[i]]!=old){
			dict[num[i]]=++cnt;
			old=ori[num[i]];
		}else{
			dict[num[i]]=cnt;
		}
	}
///	for(int i=1;i<=n;++i)printf("%d ",dict[i]);
//	printf("\n");
	for(int i=1;i<=n;++i){
		update1(dict[i]);
		before[i]=sum1(dict[i]-1);
	}
	memset(c,0,sizeof(c));
	long long tot=0;
	for(int i=n;i>=1;--i){
		update2(dict[i]);
		tot+=sum2(dict[i]+1)*before[i];
	}
	printf("%lld",tot);
//	fclose(stdin);fclose(stdout);
	return 0;
}