21.09.10模拟 朗格拉日计数

给定一个环，求所有三元严格上升子序列数量 （顺时针方向）
如果是一个序列，很显然可以用树状数组做，一个环也可以。显然断环的话是n^2logn，承受不了，复制两边不会

我们用123表示三个数字的大小关系，越大表示原数越大
我们以中间的数字为中心，因为是环形的，所以一共有三个情况 1 2 3 ， 2 3 1 ， 3 1 2，就是123的三种情况的圆排列，123很好求，231不好求，我们可以用容斥原理 231的方案数就是 * * 1- 321 =231
312=3 * * - 321
树状数组维护每个数字前面大于小于，后面大于小于该数的个数即可

#include<iostream>
#include<cstdio>
#include<cstring>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
#define bug cout<<"~~~~~~~~~~~~~"<<'
';
#define bugout(x) cout<<x<<endl;
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x, char cc) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar(cc);
}
const int N = 5e5 + 79;
int n;
int a[N];
lxl ans;
struct BIT {
	int c[N];
	inline int lowbit(int x) {
		return x & -x;
	}
	inline void add(int x, int y) {
		for(; x <= n; x += lowbit(x)) {
			c[x] += y;
		}
	}
	inline int query(int x) {
		int tot(0);
		for(; x; x -= lowbit(x)) {
			tot += c[x];
		}
		return tot;
	}
	inline void init() {
		memset(c, 0, sizeof c);
	}
} B;
#define int long long
int presmall[N], prebig[N]; 
int sufsmall[N], sufbig[N]; 
// a,b,c
main() {
	freopen("counter.in", "r", stdin);
	freopen("counter.out","w",stdout);
	read(n);
	rep(i, 1, n) {
		read(a[i]);
	}

	B.init();
	rep(i, 1, n) {
		presmall[i] = B.query(a[i] - 1);
		prebig[i] =  i - 1 - presmall[i];
		B.add(a[i], 1);
	}
	B.init();
	drp(i, n, 1) {
		sufsmall[i] = B.query(a[i] - 1);
		sufbig[i] = n - i - sufsmall[i];
		B.add(a[i], 1);
	}
	lxl ans(0), now(0);
	rep(i, 1, n) {
		ans += 1ll * presmall[i] * sufbig[i];//123
		now = 1ll * prebig[i] * sufsmall[i];//321

		ans += 1ll * prebig[i] * (prebig[i] - 1) / 2 - now;//231
		ans += 1ll * sufsmall[i] * (sufsmall[i] - 1) / 2 - now;//312
	}
	out(ans, '
');
	return 0;
}