记录编号	49927	评测结果	AAAAAAWTTT
题目名称	三元数对	最终得分	60
用户昵称	feng	是否通过	未通过
代码语言	C++	运行时间	3.793 s
提交时间	2012-11-09 20:57:07	内存使用	4.57 MiB

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAX=31000;
long long t[MAX],a[MAX],tmpr[MAX],tmpl[MAX],fl[MAX],fr[MAX];
long long sum,i,n;
void merge(int l,int mid,int r)
{
	int p=l;
	int i=l,j=mid+1,s=0;
	while(i<=mid&&j<=r)
	{
		if(a[i]<a[j])
		{
			tmpl[p]=fl[i]+s;
			tmpr[p]=fr[i];
			t[p++]=a[i++];
		}
		else{
			tmpl[p]=fl[j];
			tmpr[p]=fr[j]+(mid-i+1);
			s++;
			t[p++]=a[j++];
		}
	}
	while(i<=mid){	tmpl[p]=fl[i]+s;	tmpr[p]=fr[i];	t[p++]=a[i++];}
	while(j<=r){	tmpl[p]=fl[j];	tmpr[p]=fr[j];  t[p++]=a[j++];}
	for(i=0;i<p;i++){	a[i]=t[i];fl[i]=tmpl[i];fr[i]=tmpr[i];}
}
void mergesort(int l,int r)
{
	if(l<r)
	{
		int mid=(r-l)/2+l;	
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r);
	}
}
int main()
{
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	mergesort(1,n);
	long long ans=0,l=0,r=0;
	for (i=1;i<=n;i++)
    {
       l=i-1-fl[i];
       r=(n-i)-fr[i];
       ans=ans+l*r;
    }
	printf("%d",ans);
	return 0;
}