Note - 单 log 求排列全局三维偏序数量
考虑容斥计数。
令 \(f_c\) 为恰好 \(c\) 维偏序的数量。
那么考虑 \(i\) 若对于 \(j\) 是 \(x\) 维偏序，那么 \(j\) 对于 \(i\) 就是 \(3 - x\) 维偏序。
于是可以知道有 \(f_0 = f_3, f_1 = f_2\)，进一步可以推出 \(f_2 + f_3 = \frac{n(n - 1)}{2}\)。
那么接下来就要向 \(f_2, f_3\) 来靠拢。
考虑令 \(S_1 = \{(i, j) | a_i < a_j, b_i < b_j\}, S_1 = \{(i, j) | a_i < a_j, c_i < c_j\}, S_1 = \{(i, j) | b_i < b_j, c_i < c_j\}\)。
那么求 \(|S_1|, |S_2|, |S_3|\) 是简单的，二维偏序即可。
考虑 \(S = |S_1| + |S_2| + |S_3|\) 的构成，分析可以知道是 \(f_2 + 3 f_3\)。
那么就有等式 \(\begin{cases}f_2 &+ & f_3 & = &\frac{n(n - 1)}{2}\\ f_2 &+ &3f_3 & = & S&\end{cases}\)。
于是可以知道 \(f_3 = \dfrac{S - \frac{n(n - 1)}{2}}{2}\)。
那么就可以通过跑 \(3\) 次二维偏序，在 \(\mathcal{O}(n\log n)\) 的复杂度内求出全局三维偏序数量了。
试图扩展到 \(4\) 维偏序。
大概有 \(\begin{cases}f_2 & + & 2f_3 & + & 2f_4 & = & n(n - 1) & \\ f_2 & + & 3f_3 & + & 6f_4 &= & S_1 & \\ 0 & + & f_3 & + & 4f_4 & = & S_2 &\end{cases}\)
然后会发现解出了 \(S_1 - S_2 = n(n - 1)\)，成功寄了。
好像扩展到 \(2k + 1\) 维偏序都是可行的。
但是在 \(k \ge 2\) 的情况下明显就不如 bitset 了呀。