记录编号 233229 评测结果 AAWWWWWWWW
题目名称 三元数对 最终得分 20
用户昵称 Gravatarliu_runda 是否通过 未通过
代码语言 C++ 运行时间 0.036 s
提交时间 2016-03-04 11:10:28 内存使用 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);
}*/
void swap(int a,int b){
	int tmp=num[a];
	num[a]=num[b];
	num[b]=tmp;
}
void quicksort(int l,int r){
//	printf("qs(%d %d)",l,r);
	if(r-l<=1)return;
	int i=l+1,j=l+1;
	while(j<r){
		if(ori[num[j]]>ori[num[l]])j++;
		else{
			swap(i,j);
			i++;j++;
		}
	}
//	for(int i=l;i<r;++i)printf("%d ",num[i]);
//	printf("\n");
	if(i!=r&&i!=l+1)swap(l,i);
	if(i==r){
		swap(l,i-1);
		i--;
	}
	else if(i==l+1)i--;
	quicksort(l,i);
	quicksort(i+1,r);
}
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();
	}
	quicksort(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;
}