三元上升子序列

题目

求满足 (i < j < k，a_i < a_j < a_k) 的三元组的个数

思路

考虑三元组中间的数
那么它对答案的贡献是它前面比他小的数的个数乘上它后面比他大的数的个数
树状数组维护就好了

(Code)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit (x & (-x))
#define LL long long
using namespace std;

const int N = 3e4 + 5;
int n , m , a[N] , ind[N] , c[N] , l[N] , r[N];
LL ans;

inline void add(int x){for(; x <= m; x += lowbit) c[x] += 1;}
inline int query(int x)
{
	int res = 0;
	for(; x; x -= lowbit) res += c[x];
	return res;
}

int main()
{
	scanf("%d" , &n);
	for(register int i = 1; i <= n; i++) scanf("%d" , &a[i]) , ind[i] = a[i];
	sort(ind + 1 , ind + n + 1);
	m = unique(ind + 1 , ind + n + 1) - ind - 1;
	for(register int i = 1; i <= n; i++)
	{
		int k = lower_bound(ind + 1 , ind + m + 1 , a[i]) - ind;
		l[i] = query(k - 1) , add(k);
	}
	memset(c , 0 , sizeof c);
	for(register int i = n; i; i--)
	{
		int k = lower_bound(ind + 1 , ind + m + 1 , a[i]) - ind;
		r[i] = query(m) - query(k) , add(k);
	}
	for(register int i = 1; i <= n; i++) ans += 1LL * l[i] * r[i];
	printf("%lld" , ans);
}