题目传送门：三元上升子序列

这道题先需要想到一个结论，就是$ans=\sum_{i=1}^{n}*(a[i]左边比他小的数的数量)*a[i]右边比他大的数的数量$。

就可以先离散化再2次树状数组就好了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200005],b[200005],ans;
int fuck1[200005],fuck2[200005],n,len;
int Left[200005],Right[200005];//开小数组见祖宗 
inline int lowbit(int x){return x&-x;}
inline int add1(int x){for(int i=x;i<=len;i+=lowbit(i))fuck1[i]++;}
inline int add2(int x){for(int i=x;i<=len;i+=lowbit(i))fuck2[i]++;}
inline int ask1(int x){int sum=0;for(int i=x;i;i-=lowbit(i)){sum+=fuck1[i];} return sum;}
inline int ask2(int x){int sum=0;for(int i=x;i;i-=lowbit(i)){sum+=fuck2[i];} return sum;}
signed main() {
    freopen("T2.in","r",stdin);
    freopen("T2.out","w",stdout);
	read(n);
	For(i,1,n)read(a[i]),b[i]=a[i];
	
    sort(b+1,b+n+1);
	len=unique(b+1,b+n+1)-b-1;
	For(i,1,n) a[i]=lower_bound(b+1,b+len+1,a[i])-b;//离散化

	For(i,1,n) add1(a[i]),Left[i]=ask1(a[i]-1);
	for(int i=n;i>=1;--i) add2(a[i]),Right[i]=ask2(len)-ask2(a[i]);
    
	For(i,1,n) ans+=Left[i]*Right[i];
	write(ans);
    return 0;
}