记录编号	428311	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2017-07-25 11:57:45	内存使用	1.31 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=50010;
struct cc{
	int v,t;
	int z;
	inline bool operator <(const cc &a)const {
		if(v==a.v)return t<a.t;
		return v<a.v;
	}
}caozuo[maxn];
int n;
int data[maxn];
int sl[maxn],sr[maxn];
inline void cdql(int l,int r){
	if(l==r)return ;
	int m=(l+r)>>1;
	cdql(l,m);cdql(m+1,r);
	sort(caozuo+l,caozuo+m+1);
	sort(caozuo+m+1,caozuo+r+1);
	int p=l,q=m+1;
	long long sum=0;
	while(q<=r){
		while(p<=m&&caozuo[p]<caozuo[q]&&caozuo[p].v<caozuo[q].v){
			sum++;
			p++;
		}
		sl[caozuo[q].z]+=sum;
		q++;
	}
	sum=0;
} 
inline void cdqr(int l,int r){
	if(l==r)return ;
	int m=(l+r)>>1;
	cdqr(l,m);cdqr(m+1,r);
	sort(caozuo+l,caozuo+m+1);
	sort(caozuo+m+1,caozuo+r+1);
	int p=l,q=m+1;
	long long sum=0;
	while(q<=r){
		while(p<=m&&caozuo[p]<caozuo[q]&&caozuo[p].v<caozuo[q].v){
			sum++;
			p++;
		}
		sr[caozuo[q].z]+=sum;
		q++;
	}
	sum=0; 
}
int main(){
	freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&data[i]);
		caozuo[i].v=data[i];
		caozuo[i].t=i;
		caozuo[i].z=i; 
	}
	cdql(1,n);
	int cx=0;
	for(int i=n;i>=1;i--){
		caozuo[++cx].v=data[i];
		caozuo[cx].t=cx;
		caozuo[cx].z=i;
	}
	cdqr(1,n);
	long long ans=0;
	for(int i=1;i<=n;i++){
		//cout<<data[i]<<" "<<sl[i]<<" "<<sr[i]<<endl;
		ans+=sl[i]*sr[i];
	} 
	cout<<ans<<endl;
	return 0;
}