给定三个长为 \(n\) 的序列 \(a, b, c\)，求有多少个二元组 \((i, j)\) 满足 \(a_i < a_j, b_i < b_j, c_i < c_j\)。
\(n \leq 10^6\)。
考虑对 \((a, b), (a, c), (b, c)\) 分别做一次二维偏序，设它们的偏序数之和为 \(S\)。
-
当 \((i, j)\) 形成三维偏序的时候，\((i, j)\) 在三次二维偏序里面都被统计了，对 \(S\) 的贡献是 \(3\)。
-
当 \((i, j)\) 只形成二维偏序时，\((i, j)\) 在三次二维偏序里面仅统计一次，对 \(S\) 的贡献为 \(1\)。
-
当 \((i, j)\) 形成一维偏序或者不形成偏序，那么对 \(S\) 的贡献为 \(0\)。
设形成 \(x\) 维偏序的 \((i, j)\) 集合为 \(A_x\)，那么 \(|A_3 \cup A_2| = \frac{n \times (n - 1)}{2}\)。对于 \(|A_3 \cup A_2|\) 里面的数对全部扣掉 \(1\) 的贡献，那么 \(S \gets S - \frac{n \times (n - 1)}{2}\)，\(A_2\) 中数对对 \(S\) 的贡献为 \(0\)，\(A_3\) 中数对对 \(S\) 的贡献为\(2\)。最后答案就是 \(\frac{S}{2}\)。
时间复杂度 \(O(n \log n)\)。
标签：偏序,frac,复杂度,三维,贡献,二维,nlogn From： https://www.cnblogs.com/zzxLLL/p/17813859.html