科技——$O(n\log n)$ 三维偏序

1个月前发布

问题背景

有 $n$ 个三元组 $(a_i,b_i,c_i)$，要求满足 $a_i\le a_j,b_i\le b_j,c_i\le c_j$ 的有序对 $(i,j)$ 数量。
保证不存在两个三元组相同。（存在相同的情况下面会说）。

介绍

因为不会出现重复的数，所以不需要考虑 $(i,j)$ 互相偏序的情况。

设 $f_i$ 表示恰好 $i$ 维偏序的对数，$g_i$ 表示钦定 $i$ 维偏序的对数。
那么 $g_i=\sum_{j=i}^3 C_j^i \times f_j$，二项式反演得 $f[i]=\sum_{j\ge i} (-1)^{j-i} \times C_j^i \times g_j$。
所以：$f_0=g_0-g_1+g_2-g_3$。
即 $g_3=g_0-f_0-g_1+g_2$。
而 $g_3=f_3$，所以 $f_3=g_0-f_0-g_1+g_2$。

$g_0$ 和 $g_1$ 直接 $O(1)$ 和 $O(n)$ 求，$g_2$ 做三次二维偏序就可以了。

主要是 $f_0$ 怎么算。
注意到现在偏序条件是 $\le$ 所以 $f_0$ 不一定 $=f_3$。
比如 $(4,4,4)$ 确实三维偏序 $(2,4,4)$ 但是 $(2,4,4)$ 有两维是偏序 $(4,4,4)$ 的。

所以如果我们能让每一维都变成互不相同的就可以保证 $f_0=f_3$ 了。
也就是说 $f_3=\frac{g_0-g_1+g_2}{2}$。

那怎么办呢？
其实只需要分别按某一维为第一关键字排序，其他两维为二，三关键字排序。
将这种条件下的每个三元组的排名作为这一维新的值就可以了。
举个例子：我们有三个三元组 $(4,4,2),(2,4,4),(4,4,4)$。

先按照第一维为第一关键字，二，三维为第二，三关键字排序：$(2,4,4),(4,4,2),(4,4,4)$。
然后用现在的排名替换第一维：$(1,4,4),(2,4,2),(3,4,4)$。
再按照第二维为第一关键字，一，三维为第二，三关键字排序：$(1,4,4),(2,4,2),(3,4,4)$。
然后用现在的排名替换第二维：$(1,1,4),(2,2,2),(3,3,4)$。
最后按照第三维为第一关键字，一，二维为第二，三关键字排序：$(2,2,2),(1,1,4),(3,3,4)$。
然后用现在的排名替换第三维：$(2,2,1),(1,1,2),(3,3,3)$。

容易证明这样每一维都是排列，并且不会影响 $f_3$ 最终的值。(但显然会影响 $f_0,f_1,f_2$，反正你也不去管这三个值)。
具体看最后给出的代码。

代码可能比 CDQ 分治还好写。

补充说明

如果会出现相同的三元组怎么办？
相同的三元组答案肯定一样，可以把他们缩到一起（类似于洛谷模板题的处理思路），然后在最后算答案的时候再加上互相偏序的三元组的贡献。
如果某一维要求 $\ge$ 怎么办？
把那一维全部取反即可。

局限性

不能像 CDQ 分治那样算出每个三元组具体偏序了多少其他三元组。
偏序条线必须包含 =，即不能处理 > 类型的偏序。
这一点也很好证明，因为不管你的要求是什么，按照那种方法变换之后的序列都是一样的，无法区分 $>$ 和 $\ge$。
而如果你不变换的话，$(2,4,4)$ 没有一维是偏序 $(4,4,4)$ 的，但是 $(4,4,4)$ 并不是三维偏序 $(2,4,4)$ 的。
所以 $f_0\ne f_3$。