如何以快于O(N²)的时间统计三维点集各点的支配点数量？
问题分析
你需要解决的是三维偏序计数问题：对每个点$(x_j,y_j,z_j)$，统计满足$x_k \leq x_j$、$y_k \leq y_j$、$z_k \leq z_j$的点的数量（包括点本身）。O(N²)的暴力枚举效率太低，我们可以通过降维+数据结构的方式将时间复杂度优化到O(N log²N)。
核心思路
三维偏序问题可以通过排序降维，将其转化为二维动态查询问题：
- 先按$x$坐标排序，这样处理每个点时，所有$x_k \leq x_j$的点要么已经处理过，要么和当前点$x$值相同（后续统一处理）。
- 对排序后的点，我们只需要维护一个数据结构，支持插入$(y,z)$点和查询有多少个已插入点满足$y \leq y_j$且$z \leq z_j$。
具体实现步骤
1. 点排序
将所有点按以下规则排序：
- 优先按$x$升序排列；
- 若$x$相同，按$y$升序排列；
- 若$y$也相同，按$z$升序排列。
这样排序后，对于任意点$j$，所有$x_k < x_j$的点都在$j$之前，$x_k = x_j$的点要么在$j$之前，要么和$j$同组。
2. 坐标离散化
由于$y$和$z$的取值范围可能很大（比如远大于N），直接用原始值作为数据结构的下标会浪费空间且效率低，因此需要对$y$和$z$进行离散化：
- 收集所有点的$y$值，排序后去重，得到每个$y$对应的离散化排名（rank）；
- 对$z$值执行同样的操作，得到$z$的离散化排名。
离散化后，$y$和$z$的取值范围被压缩到$[1, M]$和$[1, K]$（$M,K \leq N$），适合树状数组等结构处理。
3. 二维树状数组（Fenwick Tree）处理二维查询
我们使用二维树状数组来维护已插入的点，它支持两种操作：
- 插入操作：在位置$(y_{rank}, z_{rank})$处计数+1；
- 查询操作：查询矩形区域$[1, y_j^{rank}] \times [1, z_j^{rank}]$内的总计数，这个值就是满足$y_k \leq y_j$且$z_k \leq z_j$的点的数量。
注意：对于$x$值相同的点，我们需要先统一查询所有同$x$点的结果，再将这些点插入到树状数组中。这是因为同$x$的点之间，只有满足$y_k \leq y_j$且$z_k \leq z_j$的点才应该被计入$j$的结果，如果先插入再查询，会导致同$x$但$y,z$更大的点被错误计入。
时间复杂度分析
- 排序的时间复杂度是$O(N \log N)$；
- 离散化的时间复杂度是$O(N \log N)$；
- 每个点的插入和查询操作都是$O(\log M \log K)$，由于$M,K \leq N$，所以这部分总时间是$O(N \log^2 N)$。
整体时间复杂度为$O(N \log^2 N)$，远优于$O(N^2)$的暴力解法。
替代方案：CDQ分治
如果觉得二维树状数组实现起来比较繁琐，也可以用CDQ分治来解决这个问题，时间复杂度同样是$O(N \log^2 N)$。其核心思路是通过分治将三维偏序拆解为多个二维偏序问题，再用一维树状数组处理二维查询，常数可能比二维树状数组更小。
内容的提问来源于stack exchange，提问作者sundeco
