分治的三步骤是？
考点：分治三步骤（A1）。
解析：分解（拆子问题）→ 解决（递归求解）→ 合并（组合子解）。✅ 正确
排除法：B/C/D 都不是分治骨架。
关联 · A2 主定理：三步骤决定复杂度。
判断题：主定理思想—— 的解是 （归并排序）， 是 （二分）。
考点：主定理思想（A2）。
解析： 是 （归并）； 是 （二分）。✅ 正确
排除法：无（判断题）。混淆点：分解次数 × 每层代价。
关联 · A3 分治回顾：各算法的复杂度来源。
判断题：快排、归并、快速幂都是分治——快排先分后治、归并先治后合、快速幂每次把指数砍半。
考点：分治回顾（A3）。
解析：快排先分后治、归并先治后合、快速幂指数砍半——都是分治。✅ 正确
排除法：无（判断题）。混淆点：合并步骤的有无是三者差异。
关联 · 第 19 章分治：快排归并的深入版。
判断题：二分/三分是"只留一半"的退化分治；二分答案则是"对答案二分 + check 验证"的套壳。
考点：与二分区别（A4）。
解析：二分/三分是"只留一半"的退化分治；二分答案是"对答案二分 + check"的套壳。✅ 正确
排除法：无（判断题）。混淆点：分治拆多份、二分拆两份。
关联 · B/C 组：二分家族两员。
判断题：分治要求子问题独立且同构——子问题互不依赖、结构相同，才能递归解决后合并。
考点：适用条件（A5）。
解析：子问题独立且同构——互不依赖、结构相同，才能递归解决后合并。✅ 正确
排除法：无（判断题）。混淆点：不独立（如 DP 依赖）就不能分治。
关联 · A6 总表：适用即一切。
分治进阶总表是？
考点：进阶总表（A6）。
解析：二分查找 / 二分答案 / 三分 / CDQ / 整体二分 / 分治应用。✅ 正确
排除法：B/C/D 以偏概全。
关联 · 本章各板块：总表即目录。
二分查找（左闭右开）的标准模板是？
考点：二分模板（B1）。
解析：while (l < r)，a[mid] >= x → r = mid 否则 l = mid + 1，返回 l（第一个 ≥x）。✅ 正确
排除法：B 边界不配套；C/D 不是二分。
关联 · B4 边界条件：模板与边界配套。
lower_bound 的语义是？
考点：lower_bound 语义（B2）。
解析：返回第一个 的位置。✅ 正确
排除法：B 是 upper_bound；C/D 无依据。
关联 · I1 代码：{1,3,5,7,9} 找 5 → 3。
判断题：lower_bound 找第一个 、upper_bound 找第一个 ——两者之差 = x 的出现次数。
考点：上界与下界（B3）。
解析：lower_bound 第一个 ≥x、upper_bound 第一个 >x——两者之差 = x 出现次数。✅ 正确
排除法：无（判断题）。混淆点：I3/I4 实测 3 与 6。
关联 · I3/I4 代码：{1,3,5,5,5,7} 的 3 与 6。
判断题：模板边界必须配套——r = mid 配 l = mid + 1（左闭右开）；l = mid 配 mid = (l + r + 1) / 2（找最后一个满足）。
考点：边界条件（B4）。
解析：r = mid 配 l = mid + 1（左闭右开）；l = mid 配 mid = (l+r+1)/2（找最后一个满足）。✅ 正确
排除法：无（判断题）。混淆点：不配套 = 死循环（P1）。
关联 · P1 死循环：边界不配套实证。
判断题：mid = l + (r - l) / 2 防溢出——(l + r) / 2 在 l、r 接近 int 上限时相加溢出。
考点：mid 防溢出（B5）。
解析：mid = l + (r-l)/2——(l+r)/2 在接近 int 上限时溢出。✅ 正确
排除法：无（判断题）。混淆点：负值场景也可用 (l+r)>>1（正数时）。
关联 · I5 填空：防溢出的写法。
判断题：二分变体——第一个 ≥x、第一个 >x、最后一个 <x、最后一个 ≤x，本质都是同模板改比较符与更新方向。
考点：二分变体（B6）。
解析：第一个 ≥x、第一个 >x、最后一个 <x、最后一个 ≤x——同模板改比较符与更新方向。✅ 正确
排除法：无（判断题）。混淆点：变体多，模板只有一个。
关联 · B1 模板：模板为纲。
判断题：二分查找 ——每次把区间砍半， 个元素最多比较约 次。
考点：复杂度（B7）。
解析：——每次砍半，最多约 次比较。✅ 正确
排除法：无（判断题）。混淆点： 规模只要约 30 次。
关联 · C 组二分答案：check 叠加后 。
二分答案的框架思想是？
考点：框架思想（C1）。
解析：答案单调 → 对答案二分 → check(mid) 判断行不行 → 收敛到最优。✅ 正确
排除法：B 对数组二分是二分查找；C/D 无依据。
关联 · J 组代码：数列分段/木材/牛栏三实例。
判断题：二分答案的前提是单调性——"mid 可行 ⟹ 更小/更大的也可行"，没有单调性就不能二分。
考点：单调性前提（C2）。
解析：check 单调是二分答案的前提——没有单调性就不能二分。✅ 正确
排除法：无（判断题）。混淆点：先证单调再二分（H2）。
关联 · H2 check 单调性：前提被破坏的后果。
check(mid) 函数的作用是？
考点：check 函数（C3）。
解析：贪心/模拟判断"答案 ≤ mid 能不能做到"， 一次。✅ 正确
排除法：B/C/D 都不是 check 的职责。
关联 · O7 填空：贪心分段 check。
判断题：最大化最小值（答案越大越好）用 mid = (l + r + 1) / 2，可行则 l = mid——防死循环的关键是 mid 向上取整。
考点：最大化最小（C4）。
解析：答案越大越好 → mid = (l+r+1)/2 向上取整、可行 l = mid——防死循环。✅ 正确
排除法：无（判断题）。混淆点：J4 填空即此式。
关联 · J3 牛栏：最大化最小距离 3。
判断题：最小化最大值（答案越小越好）用 mid = (l + r) / 2，可行则 r = mid——与最大化最小正好对称。
考点：最小化最大（C5）。
解析：答案越小越好 → mid = (l+r)/2、可行 r = mid——与最大化最小对称。✅ 正确
排除法：无（判断题）。混淆点：J1 数列分段用此式。
关联 · J1 数列分段：最小化最大段和 6。
判断题：实数二分不用纠结边界——for (int i = 0; i < 100; i++) 固定迭代 100 次，精度远超要求。
考点：实数二分（C6）。
解析：固定迭代 100 次，精度远超要求——不用纠结边界。✅ 正确
排除法：无（判断题）。混淆点：J5 实测 sqrt(2) 得 1.414214。
关联 · J5 代码：实数二分实例。
判断题：例题思想——跳石头、数列分段（最小化最大段和）、木材切割、牛栏（最大化最小距离）全是"二分答案 + 贪心 check"。
考点：例题思想（C7）。
解析：跳石头、数列分段、木材切割、牛栏全是"二分答案 + 贪心 check"。✅ 正确
排除法：无（判断题）。混淆点：check 几乎总是贪心。
关联 · J 组三题：例题即代码组。
单峰函数是？
考点：单峰函数（D1）。
解析：先单调变化再反向（只有一个极值点）——三分的前提。✅ 正确
排除法：B 任意函数三分会漏；C/D 是特例。
关联 · D3 适用条件：单峰才三分。
三分查找的核心思想是？
考点：三分思想（D2）。
解析：取两个三分点 mid1 < mid2，比较函数值后丢掉三份中的一份。✅ 正确
排除法：B 是中点（二分）；C/D 无依据。
关联 · K1 代码：f=(x-2)² 得 2。
判断题：三分适用于单峰函数（凸/凹均可）；多峰函数三分会漏掉真正的全局极值。
考点：适用条件（D3）。
解析：只适用单峰函数（凸/凹均可）；多峰函数会漏全局极值。✅ 正确
排除法：无（判断题）。混淆点：H3 反面——连续 ≠ 可三分。
关联 · H3 三分条件：反面题呼应。
判断题：二分靠"单调性"、三分靠"单峰性"——二分每次砍一半、三分每次砍三分之一（常数更大）。
考点：与二分对比（D4）。
解析：二分靠单调性、三分靠单峰性——每次砍三分之一（常数更大）。✅ 正确
排除法：无（判断题）。混淆点：同阶 。
关联 · D6 复杂度：常数差异。
判断题：三分只能求极小值，不能求极大值。
考点：求极大（D5）。
解析：三分既能求极小也能求极大——把更新规则反过来即可。"只能求极小"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：K2 实测求极大得 4。
关联 · K2 代码：极大值 4。
判断题：三分复杂度 （同阶二分，常数约大 1.7 倍）——区间每次乘 收缩。
考点：复杂度（D6）。
解析：（同阶二分，常数约大 1.7 倍）——区间每次乘 2/3。✅ 正确
排除法：无（判断题）。混淆点：。
关联 · D4：常数差异的量化。
判断题：浮点三分用固定迭代次数（如 200 次）或 r - l > eps 判断收敛，注意 eps 别小于浮点精度。
考点：浮点三分（D7）。
解析：固定迭代次数或 r - l > eps 收敛，eps 别小于浮点精度。✅ 正确
排除法：无（判断题）。混淆点：K6 实测 |x-1| 得 1.000000。
关联 · K6 代码：浮点三分实例。
判断题：三维偏序（ 且 且 ）用 CDQ 分治——按 a 排序后，分治解决 b 维、数据结构解决 c 维。
考点：三维偏序思想（E1）。
解析：a 排序后分治解决 b 维、数据结构解决 c 维。✅ 正确
排除法：无（判断题）。混淆点：三维 = 排序 + 分治 + 数据结构三层。
关联 · E4 树状数组：c 维的武器。
判断题：CDQ 分治的核心动作——左半对右半的贡献：左半按 b 排序、右半按 b 排序，双指针合并统计。
考点：CDQ 分治排序（E2）。
解析：左半对右半的贡献——两半各自按 b 排序，双指针合并统计。✅ 正确
排除法：无（判断题）。混淆点："左对右"是 CDQ 的灵魂。
关联 · M3 二维偏序：简化版实例计数 2。
判断题：CDQ 分治是离线算法——所有询问必须一次性给出，不能边问边答。
考点：离线思想（E3）。
解析：CDQ 是离线算法——所有询问一次性给出。✅ 正确
排除法：无（判断题）。混淆点：不能边问边答。
关联 · F2 离线批量：整体二分同样离线。
CDQ 处理三维偏序时，第三维 c 常用？
考点：与树状数组结合（E4）。
解析：第三维 c 用树状数组——归并过程中按 c 插入/查询。✅ 正确
排除法：B 并查集管连通；C/D 不维护前缀计数。
关联 · M5 代码：树状数组求逆序对。
判断题：CDQ 分治适用于所有问题——任何排序/计数问题都能用它优化。
考点：适用范围（E5）。
解析：CDQ 分治不适用于所有问题——只解决"贡献可跨半合并"的离线问题。"适用于所有问题"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：适用 = 偏序/离线/可合并贡献。
关联 · E1 三维偏序：主场是偏序类。
判断题：CDQ 分治复杂度 （或带树状数组的 ）——每层合并 ，共 层。
考点：复杂度（E6）。
解析：（带树状数组 ）——每层 、共 层。✅ 正确
排除法：无（判断题）。混淆点：与归并排序同骨架。
关联 · A2 主定理：T(n)=2T(n/2)+O(n)。
判断题：整体二分的"二分"是对答案值域二分，不是对数组下标二分——所有询问共享同一次二分过程。
考点：值域二分（F1）。
解析：整体二分对答案值域二分，不是数组下标——所有询问共享一次二分。✅ 正确
排除法：无（判断题）。混淆点：二分对象是答案。
关联 · F3 核心思想：分类递归。
判断题：整体二分是离线批量算法——一次处理所有"第 k 小"类询问，避免每个询问单独二分。
考点：离线批量（F2）。
解析：一次处理所有"第 k 小"类询问，避免每个询问单独二分。✅ 正确
排除法：无（判断题）。混淆点：M6 实测批量回答 1 1 2。
关联 · M6 代码：批量询问输出。
整体二分的核心思想是？
考点：核心思想（F3）。
解析：把询问按"答案落在左半还是右半"分类递归——二分过程与询问批量合并。✅ 正确
排除法：B 逐个二分是朴素法；C/D 无依据。
关联 · M4 填空：
k -= cnt分类。
判断题：整体二分适用场景——多组"区间第 k 小"、带修改第 k 小等"答案可二分且可批量判断"的询问。
考点：适用场景（F4）。
解析：区间第 k 小、带修改第 k 小等"答案可二分且可批量判断"的询问。✅ 正确
排除法：无（判断题）。混淆点：M2 第 3 小 = 2。
关联 · M2 代码：第 k 小实例。
判断题：整体二分比"每个询问单独二分"少大量重复统计——共享二分过程，复杂度 级别。
考点：与逐次二分对比（F5）。
解析：共享二分过程少大量重复统计——复杂度 级别。✅ 正确
排除法：无（判断题）。混淆点：逐询问二分是 。
关联 · F6 复杂度：同一结论。
判断题：整体二分每层对序列做一次 统计，共 层——优于逐询问二分的 。
考点：复杂度（F6）。
解析：每层 统计、共 层——优于逐询问二分。✅ 正确
排除法：无（判断题）。混淆点：共享统计是提速关键。
关联 · F5：对比即优势。
判断题：最大子段和的分治法——跨中点子段 = 左半后缀最大 + 右半前缀最大，与两半内部取三者 max。
考点：最大子段和分治（G1）。
解析：跨中点子段 = 左半后缀最大 + 右半前缀最大，与两半内部取三者 max。✅ 正确
排除法：无（判断题）。混淆点：L1 实测得 6。
关联 · L1 代码：分治子段和 6。
判断题：最近点对分治思想——按 x 排序分两半，递归求各半最近距离 d，再检查"跨中线宽度 2d 的带状区域"。
考点：最近点对思想（G2）。
解析：按 x 分两半，递归求各半距离 d，再查跨中线宽 2d 的带状区域。✅ 正确
排除法：无（判断题）。混淆点：L6 一维版得 2。
关联 · L6 代码：一维最近点对。
快速幂的核心思想是？
考点：快速幂（G3）。
解析：指数二进制拆分——奇数乘底数、底数自乘、指数右移，。✅ 正确
排除法：B 连乘是 ；C/D 无依据。
关联 · L3 代码：2^10 = 1024。
逆序对的定义是？
考点：逆序对回顾（G4）。
解析： 且 的数对。✅ 正确
排除法：B 是 i>j；C 只相邻；D 无关。
关联 · L2 代码：归并计数 8。
判断题：棋盘覆盖问题（L 形骨牌铺满缺一角的棋盘）——分治：把棋盘四等分，缺口所在的子棋盘递归，其余三块各占一格再递归。
考点：棋盘覆盖思想（G5）。
解析：棋盘四等分，缺口所在的子棋盘递归，其余三块各占一格再递归。✅ 正确
排除法：无（判断题）。混淆点：经典分治构造题。
关联 · A1 三步骤：构造型分治。
判断题：分治应用综合——子段和/最近点对靠"跨中点合并"、快速幂靠"指数砍半"、逆序对靠"归并时计数"。
考点：应用综合（G6）。
解析：子段和/最近点对靠"跨中点合并"、快速幂靠"指数砍半"、逆序对靠"归并计数"。✅ 正确
排除法：无（判断题）。混淆点：合并步骤各不相同。
关联 · L 组应用代码：四应用实测。
判断题：二分死循环——l = mid 却配 mid = (l + r) / 2（向下取整），当 l 与 r 相邻时 mid 恒等于 l，死循环。
考点：二分死循环（H1）。
解析：l = mid 配向下取整 mid，l 与 r 相邻时 mid 恒等于 l——死循环。✅ 正确
排除法：无（判断题）。混淆点：P1 实证。
关联 · P1 代码：死循环实证。
判断题：check 不具备单调性时二分答案会收敛到错误值——先证明单调性再二分。
考点：check 单调性（H2）。
解析：check 不单调时二分收敛到错误值——先证单调再二分。✅ 正确
排除法：无（判断题）。混淆点：单调性是二分的生命线。
关联 · C2 单调性前提：概念呼应。
判断题：只要函数连续，三分就能求出全局极值。
考点：三分条件（H3）。
解析：连续不等于单峰——多峰连续函数三分会漏全局极值。"连续就能三分"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：三分要单峰，不是连续。
关联 · D3 适用条件：单峰才是前提。
判断题：CDQ 分治要处理"左对右的贡献"——边界（l==r 返回、左右有序性、同值元素）处理不当会漏算或重算。
考点：CDQ 边界（H4）。
解析：l==r 返回、左右有序性、同值元素处理——边界不当会漏算或重算。✅ 正确
排除法：无（判断题）。混淆点：偏序的等号处理最易错。
关联 · E2 CDQ 排序：细节决定成败。
判断题：以下结论全部正确——"二分模板 l<r 配 r=mid/l=mid+1；二分答案要单调 check；三分只适用单峰；快速幂 O(log b)；CDQ 与整体二分都是离线算法"。
考点：综合判断（H5）。
解析：五结论全对——二分模板 l<r 配 r=mid/l=mid+1；二分答案要单调 check；三分只适用单峰；快速幂 O(log b)；CDQ 与整体二分都是离线。✅ 正确
排除法：无（判断题）。混淆点：本章核心结论自检清单。
关联 · 本章全部核心结论：收官判断题。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int a[6] = {0, 1, 3, 5, 7, 9}; // 下标 1 起，升序 05 int x = 5; 06 int l = 1, r = 5; 07 while (l < r) { 08 int mid = (l + r) / 2; 09 if (a[mid] >= x) r = mid; 10 else l = mid + 1; 11 } 12 cout << l; // 第一个 >= 5 的位置 13 return 0; 14}
单选题：程序输出是？
考点：手写 lower_bound（I1）。
解析：{1,3,5,7,9} 找 5：mid=3 命中 → r=3；mid=2（3<5）→ l=3；l==r 返回 3。✅ 答案 C
排除法：A 2 是 3 的位置；B/D 无依据。
关联 · B1 二分模板：l<r 左闭右开。
01// 数组同 I1，查找 x = 2（不存在），输出每次的 mid： 02int l = 1, r = 5; 03while (l < r) { 04 int mid = (l + r) / 2; 05 cout << mid << " "; 06 if (a[mid] >= 2) r = mid; 07 else l = mid + 1; 08}
单选题：程序输出是？（mid 的取值序列）
考点：mid 取值序列（I2）。
解析：查 2：mid=3（5≥2→r=3）、mid=2（3≥2→r=2）、mid=1（1<2→l=2）——序列 3 2 1。✅ 答案 A
排除法：B/C/D 顺序错。
关联 · B7 复杂度：3 次即定位。
// 数组 {0,1,3,5,5,5,7}（下标 1 起），x = 5，手写 lower_bound
单选题：程序输出是？（第一个 ≥5 的位置）
考点：重复元素 lower_bound（I3）。
解析：{1,3,5,5,5,7} 第一个 ≥5 在下标 3（a[3]=5）。✅ 答案 B
排除法：A 4 是第二个 5；C 6 是 7；D 5 是值。
关联 · B3 上下界：lower 与 upper 的差。
// 数组 {0,1,3,5,5,5,7}（下标 1 起），x = 5，手写 upper_bound
// （找第一个 > 5 的位置）
单选题：程序输出是？（第一个 >5 的位置）
考点：第一个 >x（I4）。
解析：第一个 >5 是下标 6（7）。✅ 答案 C
排除法：A 4 是中间的 5；B 5 是值；D 3 是第一个 5。
关联 · B3 上下界：upper = lower(x+1)。
01while (l < r) { 02 int mid = ______; // 防溢出中点 03 if (a[mid] >= x) r = mid; 04 else l = mid + 1; 05}
单选题：横线处应填入？
考点：防溢出 mid（I5）。
解析：l + (r - l) / 2。✅ 答案 A
排除法：B 会溢出；C 无除 2；D 少了 l。
关联 · B5 mid 防溢出：填空即写法。
// 数组 {0,1,3,5,7,9}（下标 1 起），x = 6（不存在），手写 lower_bound
单选题：程序输出是？（6 应插入的位置）
考点：插入位置（I6）。
解析：6 应插在 7 前——lower_bound(6) = 4。✅ 答案 B
排除法：A 3 是 5 的位置；C/D 无依据。
关联 · B2 lower_bound 语义：不存在即插入点。
01#include <bits/stdc++.h> 02using namespace std; 03int n = 5, m = 3; 04int a[6] = {0, 4, 2, 4, 5, 1}; 05bool check(int mid) { // 每段和 <= mid 能否分成 <= m 段 06 int cnt = 1, sum = 0; 07 for (int i = 1; i <= n; i++) { 08 if (sum + a[i] > mid) { cnt++; sum = 0; } 09 sum += a[i]; 10 } 11 return cnt <= m; 12} 13int main() { 14 int l = 0, r = 16; 15 while (l < r) { // 最小化最大段和 16 int mid = (l + r) / 2; 17 if (check(mid)) r = mid; 18 else l = mid + 1; 19 } 20 cout << l; 21 return 0; 22}
单选题：程序输出是？（分成 3 段的最小最大段和）
考点：最小化最大段和（J1）。
解析：{4,2,4,5,1} 分 3 段：4+2=6、4、5+1=6 → 最大段 6；更小（5）要 5 段 ✗。✅ 答案 D
排除法：A 5 不可行；B/C 无依据。
关联 · C5 最小化最大：l+r 取中。
// 3 根木材长度 {10,20,30}，要切出 6 段等长，求最大段长
// check(len)：sum(a[i] / len) >= 6 ?
// len=10 → 1+2+3=6 ✓；len=11 → 0+1+2=3 ✗
单选题：程序输出是？
考点：最大化段长（J2）。
解析：len=10 → 1+2+3=6 段 ✓；len=11 → 0+1+2=3 ✗。✅ 答案 C
排除法：A/B 小于最优；D 11 不可行。
关联 · C4 最大化最小：向上取整 mid。
// 牛栏位置 {1,2,4,8,9}，放 3 头牛，最大化最小距离
// check(d)：贪心放牛，间距 >= d 能否放 3 头
// d=3：1、4、8 三头 ✓；d=4：1、8 两头 ✗
单选题：程序输出是？
考点：最大化最小距离（J3）。
解析：d=3：1、4、8 三头 ✓；d=4：1、8 两头 ✗。✅ 答案 B
排除法：A 2 不是最大；C 4 不可行；D 无依据。
关联 · C4：贪心 check 放牛。
01while (l < r) { // 最大化最小值：mid 要向上取整 02 int mid = ______; 03 if (check(mid)) l = mid; 04 else r = mid - 1; 05}
单选题：横线处应填入？
考点：最大化 min 的 mid（J4）。
解析：(l + r + 1) / 2 向上取整防死循环。✅ 答案 A
排除法：B 向下取整会死循环；C/D 无依据。
关联 · H1 二分死循环：取整方向的根源。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 double l = 0, r = 2, x = 2; // 求 sqrt(2) 05 for (int i = 0; i < 100; i++) { 06 double mid = (l + r) / 2; 07 if (mid * mid >= x) r = mid; 08 else l = mid; 09 } 10 cout << fixed << setprecision(6) << l; 11 return 0; 12}
单选题：程序输出是？
考点：sqrt(2) 实数二分（J5）。
解析：迭代 100 次收敛到 1.414214（四舍五入）。✅ 答案 D
排除法：A/B/C 精度或数值错。
关联 · C6 实数二分：固定次数迭代。
// 数列 {2,3,7,3} 分成 2 段，最小化最大段和
// check(mid)：每段和 <= mid 能否分成 <= 2 段
// mid=10：2+3=5、7+3=10 → 2 段 ✓；mid=9：2+3=5、7、3 → 3 段 ✗
单选题：程序输出是？
考点：两段最小最大段和（J6）。
解析：{2,3,7,3} 分 2 段：2+3=5、7+3=10 → 10；9 要 3 段 ✗。✅ 答案 B
排除法：A 9 不可行；C/D 无依据。
关联 · J1：同法换数据。
01#include <bits/stdc++.h> 02using namespace std; 03int f(int x) { return (x - 2) * (x - 2); } // 极小点在 2 04int main() { 05 int l = 0, r = 4; 06 while (r - l > 2) { 07 int mid1 = l + (r - l) / 3; 08 int mid2 = r - (r - l) / 3; 09 if (f(mid1) < f(mid2)) r = mid2; 10 else l = mid1; 11 } 12 cout << (l + r) / 2; 13 return 0; 14}
单选题：程序输出是？（极小点）
考点：整数三分求极小（K1）。
解析：f=(x-2)² 在 [0,4]：三分收敛，输出 (l+r)/2 = 2。✅ 答案 A
排除法：B 1 是更新反的结果；C/D 无依据。
关联 · D2 三分思想：两个三分点。
01// f(x) = -x² + 4x 在 [0,4]，极大点在 2、极大值 4 02// 三分求极大：if (f(mid1) < f(mid2)) l = mid1; else r = mid2; 03// 输出 f((l + r) / 2)
单选题：程序输出是？
考点：三分求极大（K2）。
解析：求极大规则收敛到 2，f(2) = 4。✅ 答案 C
排除法：A 2 是极值点；B/D 无依据。
关联 · D5 求极大：规则反过来即可。
// f(x) = (x-2)² 在 [0,4] 求极小，每轮输出 mid1、mid2： // 第 1 轮 [0,4]：mid1=1、mid2=3 // 第 2 轮 [1,4]：mid1=2、mid2=3（f(1)=f(3) 时走 l=mid1）
单选题：程序输出是？
考点：三分点序列（K3）。
解析：[0,4] 取 1、3；f(1)=f(3) 走 else → l=1；[1,4] 取 2、3。✅ 答案 B
排除法：A 第二轮起点错；C/D 顺序错。
关联 · K1：同题的过程视角。
01while (r - l > 2) { 02 int mid1 = ______; // 第一个三分点 03 int mid2 = r - (r - l) / 3; 04 ... 05}
单选题：横线处应填入？
考点：第一个三分点（K4）。
解析：mid1 = l + (r - l) / 3。✅ 答案 C
排除法：A 少了 l；B 是二分中点；D 分母错。
关联 · D2：填空即公式。
// f(x) = x² 在 [-2,2]：先减后增，是单峰函数（凹） // 输出判定结果
单选题：程序输出是？
考点：单峰判定（K5）。
解析：x² 在 [-2,2] 先减后增——单峰（凹），可三分。✅ 答案 A
排除法：B 误判；C/D 不是输出。
关联 · D3 适用条件：判定即前提。
// f(x) = |x - 1| 在 [0,4] 求极小点，浮点三分，输出 6 位小数
单选题：程序输出是？
考点：|x-1| 的极小点（K6）。
解析：浮点三分收敛到 1.000000。✅ 答案 D
排除法：A/B/C 不是极小点。
关联 · D7 浮点三分：固定迭代。
// f(x) = (x - 3)² + 1 在 [0,6]，三分求极小值（f(3) = 1）
单选题：程序输出是？
考点：极小值输出（K7）。
解析：f=(x-3)²+1 极小值 f(3)=1。✅ 答案 A
排除法：B 3 是极值点；C/D 无依据。
关联 · K1：同法换函数。
// 数组 {-2,1,-3,4,-1,2,1,-5,4}，分治求最大子段和
// 递归：左半最大、右半最大、跨中点（左后缀最大 + 右前缀最大）取三者 max
// 答案为 6（子段 4,-1,2,1）
单选题：程序输出是？
考点：分治子段和（L1）。
解析：{-2,1,-3,4,-1,2,1,-5,4} 最大子段 4,-1,2,1 = 6。✅ 答案 B
排除法：A 4 是单元素；C/D 无依据。
关联 · G1 最大子段和分治：跨中点合并。
01#include <bits/stdc++.h> 02using namespace std; 03int a[9] = {0, 3, 1, 4, 1, 5, 9, 2, 6}; 04int tmp[9]; 05long long cnt = 0; 06void merge(int l, int mid, int r) { 07 int i = l, j = mid + 1, k = l; 08 while (i <= mid && j <= r) { 09 if (a[i] <= a[j]) tmp[k++] = a[i++]; 10 else { tmp[k++] = a[j++]; cnt += mid - i + 1; } 11 } 12 while (i <= mid) tmp[k++] = a[i++]; 13 while (j <= r) tmp[k++] = a[j++]; 14 for (int x = l; x <= r; x++) a[x] = tmp[x]; 15} 16void msort(int l, int r) { 17 if (l >= r) return; 18 int mid = (l + r) / 2; 19 msort(l, mid); msort(mid + 1, r); 20 merge(l, mid, r); 21} 22int main() { msort(1, 8); cout << cnt; return 0; }
单选题：程序输出是？（逆序对个数）
考点：归并计数（L2）。
解析：{3,1,4,1,5,9,2,6} 逆序对 8（3:1,1,2；4:1,2；5:2；9:2,6）。✅ 答案 D
排除法：A/B/C 漏数。
关联 · G4 逆序对回顾：mid-i+1 计数。
01#include <bits/stdc++.h> 02using namespace std; 03long long qpow(long long a, long long b) { 04 long long res = 1; 05 while (b) { 06 if (b & 1) res *= a; 07 a *= a; 08 b >>= 1; 09 } 10 return res; 11} 12int main() { cout << qpow(2, 10); return 0; }
单选题：程序输出是？
考点：qpow(2,10)（L3）。
解析：2^10 = 1024。✅ 答案 C
排除法：A/B/D 是 2 的其他次方。
关联 · G3 快速幂：二进制拆分。
// 3^5 mod 7：3^5 = 243，243 mod 7 = 5
单选题：程序输出是？
考点：3^5 mod 7（L4）。
解析：3^5 = 243，243 ÷ 7 = 34 余 5——快速幂每步取模，输出 5。✅ 答案 A
排除法：B 3 是底数；C/D 无依据。
关联 · L3：取模版。
01while (i <= mid && j <= r) { 02 if (a[i] <= a[j]) tmp[k++] = ______; // 取左半元素 03 else { tmp[k++] = a[j++]; cnt += mid - i + 1; } 04}
单选题：横线处应填入？
考点：取左半元素（L5）。
解析：a[i] <= a[j] 时取 a[i++]（稳定排序的关键）。✅ 答案 B
排除法：A 会取右半；C/D 无依据。
关联 · L2：填空即归并核心。
// 一维最近点对：数轴上 {1,10,12}，最近两点 10 与 12，距离 2
单选题：程序输出是？
考点：一维最近点对（L6）。
解析：{1,10,12} 最近两点 10、12，距离 2。✅ 答案 C
排除法：A 1 是 1 到 10 的一半；B 9 是 1 到 10；D 11 是 1 到 12。
关联 · G2 最近点对思想：一维版思想。
// 归并排序 {3,1,4,1,5,9,2,6}，输出排序结果
单选题：程序输出是？
考点：归并结果（M1）。
解析：排序后 1 1 2 3 4 5 6 9。✅ 答案 A
排除法：B 1 落尾；C 降序；D 未排序。
关联 · L2：同算法不同输出。
// 数组 {3,1,4,1,5,9,2,6}，整体二分求第 3 小的数
// 排序后 {1,1,2,3,4,5,6,9}，第 3 小 = 2
单选题：程序输出是？
考点：第 3 小（M2）。
解析：排序后第 3 个是 2。✅ 答案 B
排除法：A 1 是第 1/2 小；C/D 无依据。
关联 · F4 适用场景：第 k 小是主场。
// 点 (1,2)、(2,1)、(3,3)，统计 i<j 且 xi<xj 且 yi<yj 的数对 // (1,2)-(3,3) ✓、(2,1)-(3,3) ✓ → 共 2
单选题：程序输出是？
考点：偏序对计数（M3）。
解析：(1,2)-(3,3)、(2,1)-(3,3) 两对满足双小于。✅ 答案 C
排除法：A 1 漏；(1,2)-(2,1) 不满足（2>1）；D 无依据。
关联 · E2 CDQ 排序：二维版实例。
01if (cnt >= k) 询问归入左半; 02else { 03 ______; // k 减去左半贡献 04 询问归入右半; 05}
单选题：横线处应填入？
考点：k 的调整（M4）。
解析：答案在右半 → k -= cnt 扣除左半贡献。✅ 答案 A
排除法：B 方向反；C/D 语义错。
关联 · F3 核心思想：分类递归。
// 树状数组求逆序对：{3,1,4,1,5,9,2,6}（离散化后按值插入统计）
单选题：程序输出是？
考点：树状数组逆序对（M5）。
解析：{3,1,4,1,5,9,2,6} 逆序对 8（与归并同值）。✅ 答案 D
排除法：A/B/C 漏数。
关联 · E4 与树状数组结合：第三维武器。
// 数组 {3,1,4,1,5,9,2,6}，整体二分批量回答 k=1、k=2、k=3 的询问
// 答案分别为 1、1、2
单选题：程序输出是？
考点：批量询问（M6）。
解析：k=1、2、3 的答案 1、1、2。✅ 答案 B
排除法：A 3 不是第 3 小；C/D 顺序错。
关联 · F2 离线批量：一次处理多个询问。
// {1,3,5,7,9} 中 lower_bound(7) 的位置
单选题：程序输出是？
考点：lower_bound(7)（N1）。
解析：{1,3,5,7,9} 中 7 在下标 4。✅ 答案 C
排除法：A 3 是 5；B 5 是值；D 无依据。
关联 · I1：同法换 x。
// {10,20,30} 切 6 段等长，最大段长
单选题：程序输出是？
考点：最大段长（N2）。
解析：{10,20,30} 切 6 段 → 10。✅ 答案 B
排除法：A 9 非最大；C/D 不可行。
关联 · J2：同题回顾。
// f(x) = (x-2)² 在 [0,4]，三分求极小点
单选题：程序输出是？
考点：极小点（N3）。
解析：f=(x-2)² 在 [0,4] 是单峰凹函数，三分逐轮收缩区间，最终输出极小点 2。✅ 答案 A
排除法：B 1 是更新规则写反的结果；C/D 无依据。
关联 · K1：同题回顾。
// qpow(2, 10)
单选题：程序输出是？
考点：2^10（N4）。
解析：2^10 = 1024——快速幂把指数 10 拆成二进制 1010 处理，4 次自乘加 2 次累乘。✅ 答案 D
排除法：A 512 是 2^9；B 100 无依据；C 2048 是 2^11。
关联 · L3：同题回顾。
01bool check(int mid) { 02 int cnt = 1, sum = 0; 03 for (int i = 1; i <= n; i++) { 04 if (sum + a[i] > mid) { cnt++; sum = ______; } // 另起一段 05 else sum += a[i]; 06 } 07 return cnt <= m; 08}
单选题：横线处应填入？
考点：另起一段（N5）。
解析：超限时 sum = a[i] 另起一段。✅ 答案 A
排除法：B 0 需配合后续累加写法；C/D 无依据。
关联 · C3 check 函数：贪心分段核心行。
// {4,2,4,5,1} 分 3 段，最小化最大段和
单选题：程序输出是？
考点：最小最大段和（N6）。
解析：{4,2,4,5,1} 3 段 → 6。✅ 答案 B
排除法：A 5 不可行；C/D 无依据。
关联 · J1：同题回顾。
01int l = 1, r = n; 02while (①) { // 左闭右开写法 03 int mid = (l + r) / 2; 04 if (a[mid] >= x) r = mid; 05 else l = mid + 1; 06}
单选题：①处应填？
考点：循环条件（O1）。
解析：左闭右开写法 l < r。✅ 答案 C
排除法：A 配 r=mid 会死循环；B/D 语义错。
关联 · B1 模板：填空即模板行。
01if (a[mid] >= x) r = mid; 02else l = ①; // 左边界右移
单选题：①处应填？
考点：左边界更新（O2）。
解析：l = mid + 1。✅ 答案 A
排除法：B 会死循环；C 漏数；D 无依据。
关联 · B4 边界条件：配套更新。
01while (l < r) { // 最小化最大值 02 int mid = (l + r) / 2; 03 if (check(mid)) r = mid; 04 else l = ①; 05}
单选题：①处应填？
考点：不可行时更新（O3）。
解析：l = mid + 1（mid 已证不可行）。✅ 答案 B
排除法：A 死循环；C 漏数；D 无依据。
关联 · C5 最小化最大：对称更新。
01while (r - l > 2) { 02 int mid1 = ①; 03 int mid2 = r - (r - l) / 3; 04 ... 05}
单选题：①处应填？
考点：mid1 公式（O4）。
解析：l + (r - l) / 3。✅ 答案 D
排除法：A 少 l；B 二分；C 是 mid2 公式。
关联 · K4：同空再考。
01while (b) { 02 if (b & 1) res = res * a % mod; 03 a = a * a % mod; 04 ①; // 指数右移一位 05}
单选题：①处应填？
考点：指数右移（O5）。
解析：指数按位处理，每轮右移一位：b >>= 1。✅ 答案 C
排除法：A b-- 会打乱二进制拆分（P5 实证输出 32）；B/D 无依据。
关联 · G3 快速幂：核心行。
01// 归并完成后把 tmp 写回原数组： 02for (int x = l; x <= r; x++) a[x] = ①;
单选题：①处应填？
考点：tmp 回写（O6）。
解析：a[x] = tmp[x]。✅ 答案 B
排除法：A 偏移错；C 自身；D 反向偏移。
关联 · L2 归并：回写步骤。
01bool check(int mid) { 02 int cnt = 1, sum = 0; 03 for (int i = 1; i <= n; i++) { 04 if (sum + a[i] > mid) { cnt++; sum = ①; } 05 sum += a[i]; 06 } 07 return cnt <= m; 08}
单选题：①处应填？（先清空再累加当前元素）
考点：分段清零（O7）。
解析：另起一段先清零 sum = 0 再累加当前元素。✅ 答案 A
排除法：B 会重复加；C/D 无依据。
关联 · C3 check：同 N5 的另一种写法。
01int l = 1, r = 2; // 数组 {0,1,3}，查 x = 3 02while (l < r) { 03 int mid = (l + r) / 2; 04 if (a[mid] >= 3) r = mid; 05 else l = mid; // 注意：漏了 +1 06}
单选题：程序会怎样？
考点：漏 +1 死循环（P1）。
解析：{0,1,3} 查 3：mid 恒为 1、l 永远不前进——死循环。✅ 答案 A
排除法：B/C 是正常结果；D 编译没问题。
关联 · H1 二分死循环：概念实证。
01// 求 sqrt(2)，但只迭代到精度 1e-3 就停止： 02while (r - l > 1e-3) { ... } 03// 输出 6 位小数
单选题：程序输出是？（正确结果应为 1.414214）
考点：精度不足（P2）。
解析：1e-3 精度下停在 1.414063（正确 1.414214）。✅ 答案 C
排除法：A 是正确值；B/D 无依据。
关联 · C6 实数二分：迭代次数定精度。
01// f(x) = (x-2)² 在 [0,4] 求极小，但三分更新写成了"求极大"的规则： 02// if (f(mid1) < f(mid2)) l = mid1; else r = mid2; 03// [0,4]：mid1=1、mid2=3，f 相等走 else → r=3 04// [0,3]：mid1=1、mid2=2，f(1)=1 > f(2)=0 → r=2 05// 最终输出 (0+2)/2 = 1
单选题：程序输出是？（正确极小点应为 2）
考点：规则用反（P3）。
解析：用求极大规则求极小：收敛到 1（正确极小点 2）。✅ 答案 B
排除法：A 2 是正确结果；C/D 无依据。
关联 · D5 求极大：两规则别混。
01void msort(int l, int r) { 02 if (l >= r) return; 03 int mid = (l + r) / 2; 04 msort(l, mid); 05 msort(mid + 1, r); 06 // 注意：漏掉了 merge(l, mid, r) —— 只拆不合 07} 08// 最后输出原数组
单选题：程序输出是？
考点：漏合并（P4）。
解析：只拆不合 → 数组原样 3 1 4 1 5 9 2 6。✅ 答案 D
排除法：A 是正确排序；B/C 无依据。
关联 · A1 三步骤：缺"合并"步骤。
01// 快速幂把 b >>= 1 写成了 b--： 02long long res = 1; 03while (b) { 04 if (b & 1) res *= a; 05 a *= a; 06 b--; // 注意：应为 b >>= 1 07} 08cout << qpow(2, 3); // 正确结果应为 8
单选题：程序输出是？
考点：b-- 代替 b>>=1（P5）。
解析：2^3：res 变成 2×16 = 32（正确 8）。✅ 答案 C
排除法：A 8 是正确结果；B/D 无依据。
关联 · O5 填空：错位实证。
判断题：以下五种易错写法都会导致程序出错——①二分 l = mid 漏 +1（死循环）②实数二分精度不足（答案误差大）③三分更新规则用反（收敛到错误点）④归并只拆不合（数组没排序）⑤快速幂 b-- 代替 b >>= 1（结果翻倍错误）。
考点：五种易错综合判断（P6）。
解析：五条全对——漏 +1 死循环、精度不足误差大、三分规则反收敛错点、只拆不合没排序、b-- 结果错。✅ 正确
排除法：无（判断题）。混淆点：每条对应 P1~P5 一道实证题。
关联 · P1~P5：易错清单自查。