CSCI3160 T03 · Part 2/2 归并数二维支配

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T03，第 2 部分 / 共 2 部分 · 原件 T03-分治-未核-隐藏.pdf（本地课件） p.25–45 定位：归并纵坐标时累计左侧已遇到的点，把二维支配计数降至单对数。 前后：上一份 Part 1

p.25–27：支配的方向和分割【新】

p.25 q支配p要求两个坐标都不小于p；p.26 对每个点分别输出它支配的其他点数；p.27 按x一分为二。图（p.25）：q在p右上。元素：横轴x、纵轴y。看什么：排序计数在本题是“右点数左点中较低者”，与上一题“左元素数右边较小者”角色不同。

p.28–30：只剩右对左的跨贡献

p.28 定义左P1右P2，p.29 两边递归算内部支配，p.30 还需把右点支配左点的个数加到各自答案上。严格分开x坐标时左点不能支配右点，因为横坐标条件失败。

p.31–33：同样加强返回值

p.31 每层重新按y排序加二分仍需O(nlog n)合并。p.32 改成递归同时返回按y升序结果。p.33 两列顺序P1=(p3,p1,p4,p2)，P2=(p8,p7,p5,p6)。图（p.33）：把二维点投影成两列y位置。元素：左右归属已保证x条件，纵向比较决定剩余条件。看什么：不需要凭图估数值坐标，只用已给相对顺序。

p.34–36：建立归并输出

p.34 建空合并数组，p.35 两指针从头开始，跨贡献0；p.36 首先输出右p8，前面还无左点，故其新增0。每个点的答案必须单独存储；课件显示的总count是合计演示，不能拿它替代题求的逐点数组。

p.37–39：两个较低左点已就绪

p.37 输出左p3，p.38 输出左p1，已扫过左点数2；p.39 输出右p7，为p7加2，总跨贡献2。注意课件count在前两页仍0，因为它记已完成右点的贡献总和，而不是左指针位置。

p.40–42：相同收益可以属于不同点

p.40 输出右p5，也加2，总4。p.41 输出左p4，p.42 输出左p2，已扫左点数变4，但总跨贡献仍4。不能在输出每个左点时把同一个累计量直接写成右点答案。

p.43–45：最后一个点与边界补充

p.43 输出右p6，加4，总8。p.44 得合并顺序p8,p3,p1,p7,p5,p4,p2,p6，跨贡献分别p8=0、p7=2、p5=2、p6=4。p.45 递推得到O(nlog n)。

补充／相等坐标。 原定义用≤，而“竖线两边各一半”未处理相同x。对不同坐标点，可先按(x,y)字典序排序并按下标分割，使右点若与左点x相等则y不小于左点；按y归并时相等值先处理左点，确保≤计入。此时右点仍可计左点，左点不可能同时支配字典序更后的不同点。若允许完全重复坐标，须按重复组额外计数并保留身份，不直接套用本课“不同点”的条件。预排序O(nlog n)，之后保持分区与返回y序，总界不变。

补充：返回有序表不能丢掉点的身份。 对每个点保留 (原ID,x,y,答案)；递归返回的 y 排序只改变访问顺序，答案仍写回该 ID。以原例为例，右表访问顺序是 p8、p7、p5、p6，新增依次0、2、2、4，但最终按 p5、p6、p7、p8 读答案时应重排成2、4、2、0，再与各点原内部计数相加。把归并位置当作原编号，会得到数值集合正确、对应点错误的结果。

p.27 的 k-selection 可在线性时间找到平衡分割位置；若采用上述预排序处理相等 x，则只需在 x 序列的中点分开。两种实现的目标都是平衡规模，不能在递归中按 y 排序结果的中点重新划分 x。

完整合并操作：令 i=0 表示已输出的左点数，j=0 表示已输出的右点数，B 为空；当左右都有候选时，若左点 y≤右点 y，就把左点加入 B 并让 i 加1；否则把 i 加到右点原ID的答案，再把右点加入 B 并让 j 加1。右边的尾段每点都加左边总长度，左边尾段只复制。递归已给出的内部答案始终保留；返回 B 给上层，作为该子问题全部点的 y 序列。每点进 B 一次，合并 O(n)，加上两半递归为 O(n log n)。

本辅导的“归并顺便计数”是拓展，不写入仅源自主课的记忆条目。

本讲核心考点

• 按横坐标分区，归并纵坐标时累计已经过的左点（p.25–45；C 级）。

附录

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

来源与证据

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

• 原件：T03-分治-未核-隐藏.pdf（本地课件），本部分 p.25–45；页码均为 PDF 页号。

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

• 发布状态（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：无

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