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)\) 的复杂度内求出全局三维偏序数量了。