题目描述
Erwin最近对一种叫"thair"的东西巨感兴趣。。。

在含有n个整数的序列a1,a2…an中，

三个数被称作"thair"当且仅当i<j<k且ai<aj<ak

求一个序列中"thair"的个数。

输入格式
开始一个正整数n,

以后n个数a1~an。

输出格式
"thair"的个数

输入输出样例
输入 #1 复制
4
2 1 3 4

输出 #1 复制
2

输入 #2 复制
5
1 2 2 3 4

输出 #2 复制
7

说明/提示
对样例2的说明:
7个"thair"分别是
1 2 3 1 2 4 1 2 3 1 2 4 1 3 4 2 3 4 2 3 4 约定 30%的数据n<=100
60%的数据n<=2000
100%的数据n<=30000
大数据随机生成
0<=a[i]<=max long int

有点像个二维偏序。我们可以枚举每个中间数字，计算出前面比他小的数字的个数，与后面比他多的数字的个数，这个数字的贡献值就是两个值相乘。

计算数字的个数可以线段树（权值线段树）或者树状数组。 然后这道题需要离散化。就好了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=3e4+10;
int n,a[N],t[N],b[N],res,m,t1[N],t2[N];
inline int getid(int x){
	return lower_bound(b+1,b+1+m,x)-b;
}
inline void add(int x,int v){
	for(int i=x;i<=m;i+=lowbit(i))	t[i]+=v;
}
inline int ask(int x){
	int res=0;	for(int i=x;i;i-=lowbit(i))	res+=t[i];	return res;
}
signed main(){
	cin>>n;	for(int i=1;i<=n;i++)	cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);	m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		add(getid(a[i]),1);	t1[i]=ask(getid(a[i])-1);
	}
	memset(t,0,sizeof t);
	for(int i=n;i>=1;i--){
		add(getid(a[i]),1);	t2[i]=ask(m)-ask(getid(a[i]));
	}
	for(int i=2;i<n;i++)	res+=t1[i]*t2[i];
	cout<<res<<endl;
	return 0;
}