记录编号	49799	评测结果	AAAAAAAAAA
题目名称	三元数对	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2012-11-09 12:33:43	内存使用	3.72 MiB

#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=30010;
int N,Num[MAXN];LL Ans=0LL;
LL lans[MAXN]={0LL},
   rans[MAXN]={0LL};

class SegTree
{
public:
	int l,r,mid,num;
	SegTree *lc,*rc;
}*Rootl,*Rootr;
   
inline void nxy300()
{
	for(int i=1;i<=N-2;i++)
		for(int j=i+1;j<=N-1;j++)
			for(int k=j+1;k<=N;k++)
				if(Num[i]<Num[j] && Num[j]<Num[k]) Ans++;
	cout<<Ans<<endl;
}

inline void nxy8000()
{
	LL pre,nxt;
	for(int i=1;i<=N;i++)
	{
		pre=0LL,nxt=0LL;
		for(int j=1;j<=i-1;j++)
			if(Num[j]<Num[i]) pre++;
		for(int j=i+1;j<=N;j++)
			if(Num[i]<Num[j]) nxt++;
		Ans+=pre*nxt;
	} cout<<Ans<<endl;
}

void build(SegTree *pnt,int l,int r)
{
	pnt->l=l,pnt->r=r;pnt->mid=(l+r)/2;
	pnt->num=0; if(l==r) return;
	pnt->lc=new SegTree;
	pnt->rc=new SegTree;
	build(pnt->lc,l,pnt->mid);
	build(pnt->rc,pnt->mid+1,r);
}

int NowNum;
void Insert(SegTree *pnt)
{
	if(pnt->l==pnt->r) {pnt->num++;return;}
	if(NowNum<=pnt->mid) Insert(pnt->lc);
	if(NowNum>=pnt->mid+1) Insert(pnt->rc);
	pnt->num=pnt->lc->num+pnt->rc->num; 
}

int find(SegTree *pnt,int l,int r)
{
	if(pnt->l==l && pnt->r==r) return pnt->num;
	if(r<=pnt->mid) return find(pnt->lc,l,r);
	if(l>=pnt->mid+1) return find(pnt->rc,l,r);
	return (find(pnt->lc,l,pnt->mid)+
			find(pnt->rc,pnt->mid+1,r));  
}

inline void acsolve()
{
	int Max=*max_element(Num+1,Num+1+N),
	    Min=*min_element(Num+1,Num+1+N);
	Rootl=new SegTree;
	Rootr=new SegTree;
	build(Rootr,Min,Max);
	build(Rootl,Min,Max);
	for(int i=1;i<=N;i++)
	{
		NowNum=Num[i];
		Insert(Rootl);
		if(Num[i]==Min) continue;
		lans[i]=find(Rootl,Min,Num[i]-1);
	}
	for(int i=N;i>=1;i--)
	{
		NowNum=Num[i];
		Insert(Rootr);
		if(Num[i]==Max) continue;
		rans[i]=find(Rootr,Num[i]+1,Max);
	}
	for(int i=1;i<=N;i++)
		Ans+=lans[i]*rans[i];
	cout<<Ans<<endl;
}

int main()
{
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	cin>>N;
	for(int i=1;i<=N;i++) cin>>Num[i];
	if(N<=300) {nxy300();return 0;}
	if(N<=8000) {nxy8000();return 0;}
	acsolve();
	return 0;
}