题目大意

给定一个序列，求其中三元上升子序列的个数

  • 对于 i,j,ki,j,k，若 ai<aj<aka_i < a_j < a_k，则是一个满足要求的三元对。

分析

考虑枚举中间的数 jj，设其左边有 aa 个数比它小，右边有 bb 个数比它大，则中间为 jj 的三元对个数为 abab。

至此就和逆序对类似了，离散化后用树状数组即可。

#include "template/ds/fwtree/0.hpp"

int main() {
	int n = rr();
	vector<pii> v(n + 1);
	for (int i = 1; i <= n; i++) {
		v[i] = {rr(), i};
	}
	sort(v.begin(), v.end(), [](pii a, pii b) {
		if (a.first == b.first)
			return a.second > b.second;
		return a.first < b.first;
	});
	fwtree_1<int> tr(n + 1);
	vector<ll> al(n + 1), ar(n + 1);
	for (int i = 1; i <= n; i++) {
		al[i] = tr.sum(1, v[i].second);
		tr.add(v[i].second, 1);
	}
	tr = fwtree_1<int>(n + 1);
	for (int i = n; i >= 1; i--) {
		ar[i] = tr.sum(v[i].second, n);
		tr.add(v[i].second, 1);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans += 1ll * al[i] * ar[i];
	printf("%lld\n", ans);
	return 0;
}