记录编号	131741	评测结果	AAAAAAAAAA
题目名称	三元数对	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2014-10-24 20:37:20	内存使用	1.34 MiB

#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("three.in", "r");
FILE *out = fopen("three.out", "w");
#endif
typedef long long LL;
inline void getint(int &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
}
inline void putLL(const LL &x){
	if(x < 100000000){fprintf(out, "%d", x);return;}
	int a = x / 100000000, b = x % 100000000;
	fprintf(out, "%d%08d", a, b);
}
using namespace std;
const int maxn = 30000 + 5;
inline int lowbit(const int &x){return x & (-x);}
int n, A[maxn], t[maxn], B[maxn], cnt = 1;
int C[maxn] = {0}, D[maxn] = {0};
LL loc[maxn], lower[maxn];
LL ans = 0;
inline LL get_pre(int *arr, int i){
	LL x = 0;
	while(i){
		x += arr[i];
		i ^= lowbit(i);
	}
	return x;
}
inline void A_insert1(int x){
	int L = 1, R = cnt + 1, c, i;
	while(L < R){
		c = (L + R) >> 1;
		if(B[c] == A[x])break;
		if(B[c] < A[x])L = c + 1;
		else R = c;
	}
	loc[x] = c;
	lower[x] = get_pre(C, c - 1);
	i = c;
	while(i <= cnt){
		++C[i];
		i += lowbit(i);
	}
}
inline void A_insert2(int x){
	ans += (LL)lower[x] * (get_pre(D, cnt) - get_pre(D, loc[x]));
	int i = loc[x];
	while(i <= cnt){
		++D[i];
		i += lowbit(i);
	}
}
inline void work(){
	getint(n);
	int i;
	for(i = 1;i <= n;++i){
		getint(A[i]);
		t[i] = A[i];
	}
	sort(t + 1, t + n + 1);
	B[1] = t[1];
	for(i = 2;i <= n;++i){
		while(i <= n && t[i] == B[cnt])++i;
		if(i <= n)B[++cnt] = t[i];
	}
	for(i = 1;i <= n;++i)
		A_insert1(i);
	for(i = n;i;--i)
		A_insert2(i);
}

int main(){
	work();
	putLL(ans);
	return 0;
}