导引问题

$n$ 个元素， $3$ 个属性，对于每个 $i$ 需要快速找到有多少个 $j(j\neq i)$ ，使得 $\{a_j\le a_i,\;b_j\le b_i,\;c_j\le c_i\}$

一维偏序

· $a_j\le a_i$
可以对所有元素进行排序，那么排序后的第 $i$ 个元素前就有 $i-1$ 个元素比它小

二维偏序

· $a_j\le a_i$ ， $b_j\le b_i$
先双关键字排序，排序后第一关键字已经正序，所以先不用管了
问题就变成了“当前序列中，每一个元素前面的元素的 $b$ 比它小的有多少个”

做法1-树状数组

和求逆序对是一个道理，只不过这次是找小的
对于每一个位置，都会update一下这个位置的元素，让它在树状数组中映射的一系列位置+ val
在求每一个数之前，让这个数的 res 加上查询这个数在树状数组中的前缀 query()

这样就保证了：
1.每一个更新过的的树状数组元素都是前面出现过的数。
2.每一次查询的前缀都是 $\le$ 自己的数

做法2-归并排序

我们在双关键字排序之后，虽然可以保证对 $i$ 满足二维偏序的 $j$ 都在 $i$ 的前面，但是不能保证前面的都是满足二维偏序的，因为有可能 $a_j\lt b_i$ 但是 $b_j\gt b_i$
但是既然满足的都在前面，我们只要对前面的 $b$ 再排个序就可以直接快速查询了
但我们不想浪费时间重复进行一样的操作，那么就可以在排序的时候顺带对每个位置的 res 进行获取了
想要排序的时候进行每一个位置的统计，可以使用归并排序

我们将这个数组拆成两半
由于归并的特性，此时这两半均都已经排好序了
那么我们可以使用双指针分别推动两个区间的进行
使用 $i$ 推动左指针， $j$ 推动右指针
如果 $b_i\le b_j$ 那么就推动 $i$ 并让计数器 $+1$ ，直到 $b_i\gt b_j$ 推动 $j$ ，并在推动之前让这个点的 res 加上计数器的值
那么一层层递归下去，最终每一个点的所有情况都会被考虑完，也就记录好了

三维偏序

· $a_j\le a_i$ ， $b_j\le b_i$
我们采用CDQ分治的做法
前面的都是和二维偏序的归并排序一样的做法
在第三维的时候，由于第二维每走一个数对sum + 1是不安全的
一样的道理，前面的 $c$ 不一定均满足 $c_j\le c_i$
那么我们可以用树状数组
每走一步都是满足 $a_j\le a_i$ 和 $b_j\le b_i$ 的，那么我们在计入 $j$ 位置的元素时对 $c_j$ update 一下，那么在查询前缀了的时候就保证了在满足 $a_j\le a_i$ 和 $b_j\le b_i$ 的情况下，查询的是 $c_j\le c_i$ 的点了
就是三维都满足的点了

CDQ分治算法架构

|--存入元素结构体
|--对第一关键字排序
|--归并排序
|----指针移动按第二关键字排序
|----左指针移动加入树状数组
|----右指针移动元素累加答案
|----走完没有走完的指针 |----按排序后的顺序挪进原数组
|--输出答案

例题

AcWing2815. 三维偏序
题目地址 (opens new window)
题解地址 (opens new window)

AcWing2847. 老C的任务
题目地址 (opens new window)
题解地址 (opens new window)

AcWing2819. 动态逆序对
题目地址 (opens new window)
题解地址 (opens new window)