记录编号	57207	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2013-04-07 15:54:02	内存使用	2.22 MiB

#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream fin("queueb.in");
ofstream fout("queueb.out");
const int Inf=12345678;
typedef long long ll;
ll N,A[50001],f[50001],g[50001],p[50001],q[50001],tot;
class ST{
public:
	int v,size,n;
	bool pl;
	ST *pr,*suc[2],*Nil;
	ST *GNil();
	void init(int vs){
		v=vs;
		size=n=1;
		pl=0;
		pr=suc[0]=suc[1]=Nil=GNil();
	}
	void mt(){
		if(this!=Nil)
		size=suc[0]->size+suc[1]->size+n;
	}
	void trans(ST *tar,bool place){
		pl=place;
		pr=tar;
		tar->suc[pl]=this;
	}
	void rotate(){
	ST rep=*pr;
	bool repl=pl;
		suc[!pl]->trans(pr,pl);
		pr->trans(this,!pl);
		trans(rep.pr,rep.pl);
		suc[!repl]->mt();
		mt();
	}
	void splay(){
		while(pr!=Nil){
			if(pr->pr!=Nil && pl==pr->pl)
				pr->rotate();
			rotate();
		}
	}
	ST *find_v(int fv){
	ST *p=this,*prev=this;
		while(p!=Nil && prev->v!=fv){
			prev=p;
			if(fv>p->v)
				p=p->suc[1];
			else
				p=p->suc[0];
		}
		return prev;
	}
	ST *insert(int iv){
	ST *p=find_v(iv);
		if(p->v==iv)
			p->n++,p->size++;
		else{
		ST *Nw=new ST;
			Nw->init(iv);
			Nw->trans(p,iv>p->v);
			p=Nw;
		}
		p->splay();
		return p;
	}
}*Nil;
ST *ST::GNil(){return ::Nil;}
void Initialize()
{
int i;
	fin>>N;
	for(i=1;i<=N;i++)
		fin>>A[i];
	Nil=new ST;
	Nil->init(Inf);
	Nil->size=0;
}
void Solve()
{
ll i,j;
	for(i=1;i<=N;i++){
	ST *p=Nil->suc[0]->insert(A[i]);
		f[i]=p->suc[0]->size;
	}
	Nil->init(Inf);
	Nil->size=0;
	for(i=N;i>=1;i--){
	ST *p=Nil->suc[0]->insert(A[i]);
		g[i]=p->suc[0]->size;
	}
	for(i=2;i<N;i++)
		tot+=f[i]*g[i];
	fout<<tot<<endl;
}

int main()
{
	Initialize();
	
	Solve();
	
	fin.close();
	fout.close();
	return 0;
}