【题解】Izhevsk Training Camp

Izhevsk Training Camp

给定三个长度为 $n$ 的排列 $\{a_i\},\{b_i\},\{c_i\}$，问有多少对 $(x,y)$ 满足 $a_x<a_y,b_x<b_y,c_x<c_y$
$n \le 5\times 10^6$

$\texttt{Solution}$

首先有一个非常显然的 $O(n\ log^2 \ n)$ 的 $\texttt{CDQ}$ 分治做法，但可惜复杂度太高无法通过。发现本题只需得到满足条件的二元组个数，而不需要具体知道这些二元组，因此考虑用计数题的套路。

首先设满足三项中某一项的二元组集合分别为 $S_a,S_b,S_c$。令：

$$S_{ab}=S_a \cap S_b,S_{bc}=S_b \cap S_c,S_{ac}=S_a \cap S_c,S_{abc}=S_a \cap S_b \cap S_c$$

则答案是 $|S_{abc}|$

至少满足一项的集合为 $A$，全集为 $U$，三项均不满足的集合为 $P$。根据简单容斥可得：

$$|A|=|S_a|+|S_b|+|S_c|-|S_{ab}|-|S_{bc}|-|S_{ac}|+|S_{abc}|$$

移项得：

$$|S_{abc}|=|A|-|S_a|-|S_b|-|S_c|+|S_{ab}|+|S_{bc}|+|S_{ac}|$$

又有：$|A|=|U|-|P|$。又由于题目性质可知，对于任意 $(x,y) \in S_{abc}$，有 $a_x < a_y,b_x<b_y,c_x<c_y$，则有二元组 $(y,x)$ 恰好满足 $a_y>a_x,b_y>b_x,c_y>c_x$，则 $S_{abc}$ 与 $P$ 中元素两两对应，有 $|S_{abc}|=|P|$，因此上式可化为：

$$|S_{abc}|=|U|-|S_{abc}|-|S_a|-|S_b|-|S_c|+|S_{ab}|+|S_{bc}|+|S_{ac}|$$

$$2\times |S_{abc}|=|U|-|S_a|-|S_b|-|S_c|+|S_{ab}|+|S_{bc}|+|S_{ac}|$$

$|S_a|,|S_b|,|S_c|$ 可 $O(n)$ 求，$|S_{ab}|,|S_{bc}|,|S_{ac}|$ 可通过二维偏序 $O(n\ log \ n)$ 求解，$|U|$ 可 $O(1)$ 求。

复杂度 $O(n\log n)$。