#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, a[30010], s[30010], m, f[4][30010], c[60010], ans;
ll val(int x) { return lower_bound(s+1, s+m+1, x) - s; }
ll ask(int x, ll sum = 0) {
	for(; x; x -= (x & (-x))) sum += c[x];
	return sum;
}
void add(int x, ll v) { for(; x <= m; x += (x & (-x))) c[x] += v; }
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i],  s[i] = a[i];
	sort(s+1, s+n+1);
	m = unique(s+1, s+n+1) - s - 1;
	for(int i = 1; i <= n; i++) f[1][i] = 1, a[i] = val(a[i]);
	for(int i = 2; i <= 3; i++) {
		memset(c, 0, sizeof(c));
		for(int j = 1; j <= n; j++) {
			f[i][j] = ask(a[j]-1);
			add(a[j], f[i-1][j]);
		}
	}
	for(int i = 1; i <= n; i++) ans += f[3][i];
	cout << ans << endl;
	return 0;
}

作为一个三元的上升序列，我们很容易想到子序列​枚举中间的元素​​。

我们记

• Lef[i]为 A[i]左边小于A[i]的元素个数
• Rit[i]为 A[i]右边大于A[i]的元素个数

根据乘法原理，有：

• 以A[i]为中间元素​的合法序列个数为*Lef[i]Rit[i]

如何得到Lef[] 和Rit[] 数组呢？（以Lef为例）

如果我们在枚举中间元素A[i]的过程中再次遍历A[0],A[1]...A[i-1]，那么时间复杂度将达到O(n^2)，显然超时。

换一种思路： “在i前（不含）小于A[i]的元素数量和” 等价于 “在i前（不含）小于等于A[i]的元素数量和减去A[i]（这个数值）出现的次数”。

虽然这种说法令人感到莫名其妙，但它或许可以启示我们的同学联想到“前缀和”。 前缀和的思路、“逆序对”的目标进一步让我们联想到树状数组求逆序对。按刘汝佳大神的说法，“动态更新并求解前缀和，正是树状数组的标准用法”。

我们可以用树状数组c[val]记录已经被考虑的数中小于等于val的个数，初始化为0，每次更新时，调用add(A[i],1)。

在本题中，A[i]<=INT_MAX，直接定义树状数组c[INT_MAX]显然失智，所以我们不妨离散化处理。我个人认为，离散化绝对比其他“不用离散”的方法容易想到，如果是在考场上，我们可以更加轻车熟路地用离散来处理这道题目。

POJ3928和本题是类似的，不过那一题更加友善——保证任意A[i]不同，并给出了不必离散处理的A[i]范围，有兴趣的同学可以在那一题上加强练习。

代码如下，时间复杂度O(nlogn)，空间复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+10;
int n,m;
int c1[maxn],c2[maxn];//double_tree_arr
int A[maxn],_A[maxn];//discrete_arr
int Lef[maxn],Rit[maxn];//Counter

inline int _Q(int val){//查询A[i]对应的映射值 
	return lower_bound(_A+1,_A+m+1,val)-_A;
}

inline int lowbit(int i){
	return i&(-i);
}

void add(int *C,int pos,int val){
	while(pos<=maxn){
		C[pos]+=val;
		pos+=lowbit(pos);
	}
}

int sum(int *C,int pos){
	int res=0;
	while(pos>0){
		res+=C[pos];
		pos-=lowbit(pos);
	}
	return res;
}
//以上是树状数组模板，在函数里以数组指针作参数 
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		scanf("%d",&A[i]);
		_A[i]=A[i];
	}
	sort(_A+1,_A+n+1);
	m=unique(_A+1,_A+n+1)-(_A+1);
	//小细节，我们希望映射值在i...3e4之间，所以需要减去_A+1 
	//discrete
	for(int i=1;i<=n;++i){
		add(c1,_Q(A[i]),1);
		Lef[i]=sum(c1,_Q(A[i])-1);
        //“减去A[i]出现个数”的隐式体现，就是我们只计算“A[i]-1（映射意义上）”的出现个数
	}
	for(int i=n;i>=1;--i){
		add(c2,_Q(A[i]),1);
		Rit[i]=n-i-(sum(c2,_Q(A[i]))-1);
		//小细节，计算Rit时需要注意表达式与Lef不同 
	}
	long long ans=0;
	for(int i=2;i<n;++i) ans+=Lef[i]*Rit[i];
	//“乘法原理”的显式体现 
	cout<<ans;
	return 0;
}

最后总结一下程序实现中需要注意的一些细节

• A[i]最有多maxn=3e4个不同的数值，离散后最大的映射值也不超过3e4；我们的树状数组应以max{A[i]}作为下标上界，所以我们直接使用maxn作为下标上界。
• 本人在程序里定义了两个树状数组c1，c2，并在树状数组的操作函数里用参数将它们区分开来，如果只想用一个树状数组的话，不要忘记在顺、逆两次遍历之间清空数组。
• 因为我们的树状数组只能求解“小于（等于）”的数量，所以Lef和Rit的计算必须分开。
• 同样是由于上一条原因，函数sum在逆序时计算出来的其实是“i+1...n中小于等于A[i]的元素个数”，我们把它记为K。那么在i+1...n这n-i个数字中，“小于等于A[i]”的数字出现的个数其实是K-1个（因为在位置i的A[i]不应被算进去），而这些数并不是我们需要的，于是，(n-i)-(K-1)就是我们需要的Rit[i]的值了。

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
const int N=30005;
int n,m,k,s,t,a[N],b[N],c[N];
int Lef[N],Rit[N];
void add(int x){
	for (int i=x;i<=m;i+=i&(-i)) c[i]++;
}
int query(int x){
	int ans=0;
	for (int i=x;i;i-=i&(-i)) ans+=c[i];
	return ans;
}
int 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) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	for (int i=1;i<=n;++i){
		Lef[i]=query(a[i]-1);
		add(a[i]);
	}
	memset(c,0,sizeof(c));
	for (int i=n;i>=1;--i){
		Rit[i]=query(m)-query(a[i]);
		add(a[i]);
	}
	ll ans=0;
	for (int i=1;i<=n;++i)
		ans+=(ll)Lef[i]*Rit[i];
	cout<<ans;
}