CSCI3160 L02 · Part 3/4 二维支配

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L02，第 3 部分 / 共 4 部分 · 原件 L02-Divide-and-Conquer-未核.pdf（本地课件） p.13–22 定位：把二维支配拆成左右内部和跨区贡献，识别排序与秩查询的工作。 前后：上一份 Part 2 · 下一份 Part 4

Dominance Counting

p.13 分节页。

二维支配的方向（p.14–16）【新】

p.14 Given two distinct points p and q, we say that q dominates p if $p[1]\le q[1]$ and $p[2]\le q[2]$; see the figure below:

p.14 的 $\mathbb Z$ 表示整数集合，$\mathbb Z^2$ 表示两个坐标都是整数的平面点。$p[1],p[2]$ 分别是横、纵坐标。支配（dominance）要求两项都不小，而不是只看离原点远近。

图（p.14–15）：右上方的点支配左下方的点。 元素：p.14 中 q 在 p 的右上方；p.15 八个点按横坐标依次为 $p_1$ 到 $p_8$，纵坐标从低到高依次是 $p_8,p_3,p_1,p_7,p_5,p_4,p_2,p_6$。 看什么：只统计别的点，不把自身算入；例如最右点 $p_8$ 纵坐标最低，因此一个点也不支配。

题面（同原件 · Dominance Counting · p.15）

p.15 Let P be a set of n points in $\mathbb Z^2$ with distinct x-coordinates. Find, for each point $p\in P$, the number of points in P that are dominated by p.

p.15 的原图计数：$p_1$ 为 0；$p_2$ 只支配 $p_1$，为 1；$p_3$ 为 0；$p_4$ 支配 $p_1,p_3$，为 2；$p_5$ 也为 2；$p_6$ 支配前五个点，为 5；$p_7$ 支配 $p_1,p_3$，为 2；$p_8$ 为 0。p.16 同样把课堂版目标设为 $O(n\log^2 n)$，线性合并的改进留作练习。

垂直分割与两次递归（p.17–19）

p.17 Think: How to find such $\ell$ in $O(n\log n)$ time? How about $O(n)$ time?

p.17 要按横坐标把点均分。排序后在中间两个横坐标之间放竖线，需要 $O(n\log n)$；也可用 L01 的选择找到中位横坐标，再扫描分组，得到 $O(n)$ 期望时间。讲义这句没有展开确定性线性选择；不能把 L01 的期望保证换成最坏保证。奇数规模应分成一大一小两半，讲义“两边各向上取整”的描述按其偶数示意图理解。

图（p.17–19）：竖线位于 $p_4$ 与 $p_5$ 之间。 元素：左组 $P_1=\{p_1,p_2,p_3,p_4\}$，右组 $P_2=\{p_5,p_6,p_7,p_8\}$；p.19 列出两组内部的递归计数。 看什么：左组的任意点横坐标都比右组小，因此左组不可能支配右组。

p.18 定义这两个子问题；p.19 递归返回左组计数 0、1、0、2，右组计数 0、1、0、0。左组已经完成，右组尚未计入左组贡献。这个方向性就是“只给右组补数”的理由。

横坐标条件自动满足后，只查纵坐标（p.20–22）

p.20 The x-coordinates do not matter any more!

p.20 不是说支配定义改了，而是对“右点是否支配左点”这个受限问题，横坐标不等式已经全部成立。只需判断左点的纵坐标是否不超过右点。

p.21 把左组按纵坐标排序为 $p_3,p_1,p_4,p_2$，对每个右点二分找“不超过其纵坐标”的前缀长度。$p_5$ 的界限落在 $p_1$ 与 $p_4$ 之间，得到 2；$p_6$ 得到 4；$p_7$ 得到 2；$p_8$ 得到 0。加回右组内部的 0、1、0、0，得到最终 2、5、2、0。

补充：用坐标把方向手跑一次。 自取四点 $a=(1,3),b=(2,1),c=(3,2),d=(4,3)$。按横坐标分为 {a,b} 与 {c,d}：左内部互不支配；右内部 d 支配 c，所以递归计数为 a:0,b:0,c:0,d:1。把左纵坐标排序成 [1,3]：c 的纵坐标 2 覆盖前缀 [1]，增加 1；d 的纵坐标 3 覆盖 [1,3]，增加 2。最后结果 0,0,1,3，其中 d 原来的内部贡献 1 必须留下。

注意 d 与 a 的纵坐标相等，仍算支配，因为定义使用不小于。这与上一部分逆序对的严格大于不同。讲义只要求横坐标互异，不能自行加上纵坐标也互异的假设。查询边界是第一个纵坐标严格大于当前值的位置，该位置之前的数量才是“不超过”的数量。

把原图的“递归值＋跨区值”完整列在一处（p.19–21）：

p.22 依然是两个半规模子问题，加 $O(n\log n)$ 的当前层工作，故总计 $O(n\log^2 n)$。容易错在只返回跨组计数，漏掉子问题早已算出的那个 1，即 $p_6$ 对 $p_5$ 的支配。

由 p.22 展开复杂度：令 $h=\log_2 n$，第 j 层所有子问题的排序及二分总成本为 $O(n(h-j))$，因此内部层总和为 $O(n(h+(h-1)+\cdots+1))=O(n\log^2 n)$。归纳正确性则按每个待统计点讨论：左点不可能支配右点，递归值已经最终；右点支配的目标被划成右内部与左侧两类，前者递归已算，后者由纵坐标前缀精确补齐。二者不重叠，也没有第三类目标。

本讲核心考点

• 横坐标分区后，跨贡献只需比较纵坐标（p.14–22；C 级）。

附录

本部分所需过程已在正文展开。

来源与证据

• 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

• 原件：L02-Divide-and-Conquer-未核.pdf（本地课件），本部分 p.13–22；页码均为 PDF 页号。

• 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

• 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

• 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。