记录编号	443998	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.157 s
提交时间	2017-09-01 20:58:28	内存使用	0.70 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#define mid_a ((l+r)>>1)
#define mid_b ((now->l+now->r)>>1)
const int maxn=50005;
using namespace std;
struct pstree
{
	int l,r,num;
	pstree *ls,*rs;
	pstree(){l=r=num=0;ls=rs=NULL;}
}*root[maxn];
inline int get();
pstree *build(int l,int r);
pstree *add(pstree *now,int va);
int search(pstree *now,int l,int r);
int n,mx,mi=0x7fffff;
long long all;
int N[maxn];
int main()
{
	freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	n=get();
	for(int i=1;i<=n;i++)
	{
		N[i]=get();
		mx=max(N[i],mx);
		mi=min(N[i],mi);
	}
	root[0]=build(mi,mx);
	for(int i=1;i<=n;i++)root[i]=add(root[i-1],N[i]);
	for(int i=2;i<=n-1;i++)
	{
		int temp=N[i]-1;
		if(temp<mi)continue;
		int ta=search(root[i-1],mi,temp);
		int tb=search(root[n],mi,temp);
		all+=ta*(tb-ta);
	}
	printf("%lld",all);
	return 0;
}
int search(pstree *now,int l,int r)
{
	if(now->l==l&&now->r==r)return now->num;
	else if(r<=mid_b)return search(now->ls,l,r);
	else if(l>mid_b)return search(now->rs,l,r);
	else return search(now->ls,l,mid_b)+search(now->rs,mid_b+1,r);
}
pstree *add(pstree *now,int va)
{
	pstree *p=new pstree();
	p->l=now->l;p->r=now->r;
	p->num=now->num+1;
	if(p->l==p->r)return p;
	if(va<=mid_b)
	{
		p->ls=add(now->ls,va);
		p->rs=now->rs;
	}
	else
	{
		p->ls=now->ls;
		p->rs=add(now->rs,va);
	}
	return p;
}
pstree *build(int l,int r)
{
	pstree *p=new pstree();
	p->l=l;p->r=r;
	if(l!=r)
	{
		p->ls=build(l,mid_a);
		p->rs=build(mid_a+1,r);
	}
	return p;
}
inline int get()
{
	int t=0;char j=1,c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}