【学习笔记】【自学】三维偏序 (CDQ)

[P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810)

题目描述：有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。
对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。

首先，这是一个三维偏序，我们一维一维的来思考。

第一维用 $\text{sort}$ 按 $a_i.x$ 从小到大排序，保证第一维 $a_i$ 有序。注意，题目中说是满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $，即若有重复的，则需要判重，且我们有需要求出每一个三元组 $(a_{i}.x,a_{i}.y,a_{i}.z)$它出现的次数，在后期才能进行计算，简单起见，在这里我们将三元组 $(a_{i}.x,a_{i}.y,a_{i}.z)$它出现的次数设为 $t_i$，设 $a_i$ 为去重后的数组，$n$ 为去重后的数组长度。

第二维&第三维： 用一个类似归并排序的 $\text{CDQ}$ 分治，即对于一个$\text{CDQ}(left,right)$：

若 $left=right$，则直接 $return$，此时为边界条件。

接着，递归 $\text{CDQ}(left,mid),\text{CDQ}(mid+1,right)$，把 $[left,right]$ 这个区间分成 $[left,mid]$ 和 $[mid+1,right]$。

然后，归并排序，将 $[left,mid]$ 和 $[mid+1,right]$ 这两个有序的数组合并。

设 $left_1$ 为区间 $[left,mid]$ 的左指针,$right_1$ 为区间 $[left,mid]$ 的右指针，$left_2$ 为区间 $[mid+1,right]$ 的左指针，$right_2$ 为区间 $[mid+1,right]$ 的右指针。

则当 $a_{left_1}.y \le a_{left_2}.y$ 时，又因之前按照 $a_i.x$ 排过序，即也满足 $a_{left_1}.x \le a_{left_2}.x$，即满足了题目中的要求 $a_j\le a_i$，$b_j\le b_i$，此时将树状数组中的 $a_{left_1}.z$的位置上加上 $t_i$，即有 $t_{left_1}$ 个三元组 $(a_{left_1}.x,a_{left_1}.y,a_{left_1}.z)$，即树状数组中的 $add(a_{left_1}.z,t_{left_1})$，这就是第三维，再将 $a_{left_1}$ 放入临时数组 $tmp$ 中，注意，不用在意树状数组中的求和过程，因为这样可能会阻碍你对此题的理解。

当 $a_{left_1}.y \ge a_{left_2}.y$ 时，既不满足题目的要求 $a_j\le a_i$，$b_j\le b_i$，不能放入树状数组中，否则不合题意，则将 $a_{left_2}.ans$ 加上 $\sum\limits_{i=1}^{a_{left_2}.z}f_i$，即树状数组中的 $sum(a_{left_2}.z)$，这也是第三维，再将 $a_{left_2}$ 放入临时数组 $tmp$ 中。

接着，区间 $[left,mid]$ 和 $[mid+1,right]$ 中剩余元素也是通过同样的方法。

将刚才加上的所有 $t_{i\in[l,mid]}$复原，在树状数组中即为 $\text{add}(i,t_i)$。

最后，将临时数组 $tmp$ 中的变量在赋值给 $a$，这样就完成了一次 $\text{CDQ}(left,right)$。

注意，在进行 $\text{CDQ}(1,n)$ 后，需要统计 $f(i)=d\in[0,n)$ 的数量。

用 $print_i$ 表示，则 $print_{a_i.ans+a_i.same-1}=a_i.same$ 表示 $a_i.ans+a_i.same-1$ 出现的次数加上 $a_i.same$，其中 $a_i.ans+a_i.same-1$ 表示对于 $a_i$ 的答案，因为 $a_i$ 出现的次数为 $a_i.same$，题目中求 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $，即那 $a_i.same$ 个 $a_i$ 也满足要求，即 $a_i$ 和其他 $a_i.same-1$ 个 $a_i$ 配对，即加上 $a_i.same-1$，其余 $a_i.same-1$ 个 $a_i$ 也同样，即答案都为 $a_i.ans+a_i.same-1$，就是 $print_{a_i.ans+a_i.same-1}=a_i.same$。