记录编号	233197	评测结果	AAAAAAAAAA
题目名称	1260.三元数对	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2016-03-04 10:48:10	内存使用	0.98 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 buf[30005];

void merge(int l,int r,int mid){
//	printf("m(%d %d)\n",l,r);
	int i=l,j=mid,k=0;
	while(i<mid&&j<r){
		if(ori[num[i]]<ori[num[j]]){
			buf[k++]=num[i++];
		}else{
			buf[k++]=num[j++];
		}
	}
	while(j<r)buf[k++]=num[j++];
	while(i<mid)buf[k++]=num[i++];
	memcpy(num+l,buf,(r-l)*4);
//	for(int x=l;x<r;++x)num[x]=buf[x];
}
void mergesort(int l,int r){
//	printf("ms(%d %d)\n",l,r);
	if(r-l<=1)return;
	int mid=(l+r)>>1;
	mergesort(l,mid);
	mergesort(mid,r);
	merge(l,r,mid);
}
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;
}
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();
	}
	mergesort(1,n+1);
//	for(int i=1;i<=n;++i)printf("%d ",num[i]);
//	printf("\n");
	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;
}