记录编号	39338	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.154 s
提交时间	2012-07-09 13:38:47	内存使用	0.79 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
struct node {
	int l,r,v;
	node *s[2];
};
const int INF = 1000000000;
long long n,ans;
int minn,maxn;
int a[50050],f[50050],g[50050];
node *build(int l,int r) {
	node *t = new node;
	if (l == r) {
		t->l = t->r = l;
		t->v = 0;
		return t;
	}
	int mid = (l + r) >> 1;
	t->l = l,t->r = r;
	t->s[0] = build(l,mid);t->s[1] = build(mid + 1,r);
	t->v = 0;
	return t;
}
int find(node *u,int l,int r) {
	if (u->l == l && u->r == r) return (u->v);
	int mid = (u->l + u->r) >> 1,tmp = 0;
	if (l <= mid) tmp += find(u->s[0],l,std::min(r,mid));
	if (r > mid) tmp += find(u->s[1],std::max(l,mid + 1),r);
	return tmp;
}
void insert(node *u,int v) {
	if (u->l == u->r) u->v++;
	else {
		u->v++;
		int mid = (u->l + u->r) >> 1;
		if (v <= mid) insert(u->s[0],v);
		else insert(u->s[1],v);
	}
}

int main() {
      freopen("queueb.in","r",stdin);
	freopen("queueb.out","w",stdout);
	scanf("%lld", &n);
	minn = INF;maxn = 0;
	for (int i = 1;i <= n;i++) {
		scanf("%d", &a[i]);
		minn = std::min(minn,a[i]);
		maxn = std::max(maxn,a[i]);
	}
	minn--;
	maxn++;
	node *root = build(minn,maxn);
	for (int i = 1;i <= n;i++) {
		f[i] = find(root,minn,a[i] - 1);
		insert(root,a[i]);
	}
	root = build(minn,maxn);
	for (int i = n;i >= 1;i--) {
		g[i] = find(root,minn,a[i] - 1);
		insert(root,a[i]);
	}
	for (int i = 1;i <= n;i++) 
		ans += f[i] * g[i];
	printf("%lld\n", ans);
	return 0;
}