记录编号	39340	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2012-07-09 14:36:00	内存使用	1.37 MiB

#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=55555;
typedef long long LL;
typedef int array[MAXN];
typedef long long larray[MAXN];
int N,Max,Min; 
larray lans,rans;
array Num;


inline void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++) scanf("%d\n",&Num[i]);
}

inline void baori()
{
	int bans=0;
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			for(int k=j+1;k<=N;k++)
				if(Num[j]>Num[i] && Num[j]>Num[k]) bans++;
	printf("%d\n",bans);		
}

class SegTree
{
public:
	int l,r,mid,num;
	SegTree *lc,*rc;
}*Rootl,*Rootr;

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 Tmp;
void Insert(SegTree *pnt)
{
	if(pnt->l==pnt->r) {pnt->num++;return;}
	if(Tmp<=pnt->mid) Insert(pnt->lc);
	if(Tmp>=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 solve()
{
	for(int i=1;i<=N;i++)
	{
		Tmp=Num[i];
		Insert(Rootl);
		if(Num[i]-1<Min) continue; 
		lans[i]=Find(Rootl,Min,Num[i]-1);
	}
	
	for(int i=N;i>=1;i--)
	{
		Tmp=Num[i];
		Insert(Rootr);
		if(Num[i]-1<Min) continue;
		rans[i]=Find(Rootr,Min,Num[i]-1);
	}
	long long Ans=0;
	for(int i=1;i<=N;i++)
		Ans+=lans[i]*rans[i];
	printf("%lld\n",Ans);
}

int main()
{ 
	freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	init();
	if(N<=300) {baori();return 0;}
	Max=*max_element(Num+1,Num+N+1);
	Min=*min_element(Num+1,Num+N+1);
	Rootl=new SegTree;
	Rootr=new SegTree;
	build(Rootl,Min,Max);
	build(Rootr,Min,Max);
	solve();
	return 0;
}