第 3 章递归、分治与二分#

本章目标：掌握把问题缩小、拆分、定位答案的三种基本思维：递归、分治、二分。

3.1 学习目标#

能写出递归函数的语义、参数和终止条件。
理解分治算法的拆分、解决、合并三步。
掌握归并排序、快速幂、快速排序的思想。
掌握二分查找和答案二分的循环不变量。
能识别题目中的单调性。

3.2 递归#

递归函数必须说明“这个函数返回什么”。例如阶乘：

f(n)=n!

递归定义：

f(n)=\begin{cases} 1, & n=0 \\ n \cdot f(n-1), & n>0 \end{cases}

代码：

1
long long fact(int n) {
2
    if (n == 0) return 1;
3
    return 1LL * n * fact(n - 1);
4
}

递归三要素：

函数语义。
终止条件。
规模更小的子问题。

3.3 分治#

分治的基本框架：

1
solve(problem):
2
    if problem is small:
3
        return answer directly
4
    split problem into subproblems
5
    solve each subproblem
6
    merge subanswers

3.3.1 归并排序#

归并排序把数组分成两半，分别排序，再合并。

递归式：

T(n)=2T(n/2)+O(n)=O(n\log n)

合并两个有序数组：

1
while (i < left.size() && j < right.size()) {
2
    if (left[i] <= right[j]) tmp.push_back(left[i++]);
3
    else tmp.push_back(right[j++]);
4
}

归并排序稳定，适合统计逆序对。

逆序对统计：当 right[j] 小于 left[i] 时，left[i] 到 left[end] 都和 right[j] 构成逆序对。

3.4 快速幂#

求 $a^n$ 的朴素方法是乘 n 次，复杂度 $O(n)$ 。快速幂利用：

a^n = \begin{cases} (a^{n/2})^2, & n \text{ 为偶数} \\ a \cdot a^{n-1}, & n \text{ 为奇数} \end{cases}

迭代写法：

1
long long qpow(long long a, long long b, long long mod) {
2
    long long ans = 1 % mod;
3
    while (b > 0) {
4
        if (b & 1) ans = ans * a % mod;
5
        a = a * a % mod;
6
        b >>= 1;
7
    }
8
    return ans;
9
}

复杂度： $O(\log n)$ 。

3.5 二分查找#

二分的前提是单调性。最常见问题：在有序数组中找第一个不小于 x 的位置。

定义循环不变量：答案在区间 $[l,r)$ 中。

1
int lower_bound(vector<int>& a, int x) {
2
    int l = 0, r = a.size();
3
    while (l < r) {
4
        int mid = l + (r - l) / 2;
5
        if (a[mid] >= x) r = mid;
6
        else l = mid + 1;
7
    }
8
    return l;
9
}

结束时 $l=r$ ，就是第一个满足条件的位置。

3.6 答案二分#

答案二分不是在数组中找，而是在答案范围中找。

典型形式：

\min x \quad \text{s.t.} \quad check(x)=true

如果 $check(x)$ 对 x 单调，则可二分。

例：把数组分成不超过 k 段，使每段和最大值最小。

如果最大段和限制为 x 可以完成，那么更大的 x 也可以完成。
所以 check(x) 单调。

1
bool check(long long limit) {
2
    int cnt = 1;
3
    long long sum = 0;
4
    for (int v : a) {
5
        if (v > limit) return false;
6
        if (sum + v <= limit) sum += v;
7
        else cnt++, sum = v;
8
    }
9
    return cnt <= k;
10
}

3.7 浮点二分#

浮点二分通常固定迭代次数：

1
for (int t = 0; t < 100; t++) {
2
    double mid = (l + r) / 2;
3
    if (check(mid)) r = mid;
4
    else l = mid;
5
}

不用纠结 $l+1<r$ 这种整数条件。

3.8 易错点#

递归没有终止条件。
递归参数没有变小，导致无限递归。
二分左右边界语义混乱。
mid 使用 $(l+r)/2$ 可能溢出。
答案二分的 check 不单调。
最小化最大值、最大化最小值混淆。

3.9 练习#

手写归并排序并统计逆序对。
用快速幂计算 $a^b \bmod p$ 。
写 lower_bound 和 upper_bound。
找旋转数组中的最小值。
设计一个答案二分解决“最小运输能力”问题。

ACM/OI 扩展：分治进阶、三分与整体二分#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 二分模板：最小满足#

查找最小的 x，使 check(x) 为真。

1
long long l = lo, r = hi; // 答案在 [l, r]
2
while (l < r) {
3
    long long mid = l + (r - l) / 2;
4
    if (check(mid)) r = mid;
5
    else l = mid + 1;
6
}
7
cout << l << '
8
';

要点：

适用于 false false true true。
hi 必须保证可行。
返回 l 时 l==r。

2. 二分模板：最大满足#

查找最大的 x，使 check(x) 为真。

1
long long l = lo, r = hi;
2
while (l < r) {
3
    long long mid = l + (r - l + 1) / 2;
4
    if (check(mid)) l = mid;
5
    else r = mid - 1;
6
}
7
cout << l << '
8
';

要点：

适用于 true true false false。
向上取中避免死循环。

3. 三分搜索#

当函数在区间上单峰时可用三分。整数三分常用于凸/凹离散函数。

1
while (r - l > 3) {
2
    int m1 = l + (r - l) / 3;
3
    int m2 = r - (r - l) / 3;
4
    if (f(m1) < f(m2)) l = m1; // 求最大值
5
    else r = m2;
6
}
7
int ans = l;
8
for (int i = l + 1; i <= r; ++i) if (f(i) > f(ans)) ans = i;

要点：

只适用于单峰，不是所有优化都能三分。
整数三分最后要暴力扫小区间。

4. Meet-in-the-middle 折半搜索#

当 n 在 40 左右， $2^n$ 太大但 $2^{n/2}$ 可接受时使用。

1
vector<long long> gen(vector<int> b) {
2
    vector<long long> res;
3
    int m = b.size();
4
    for (int mask = 0; mask < (1 << m); ++mask) {
5
        long long s = 0;
6
        for (int i = 0; i < m; ++i) if (mask >> i & 1) s += b[i];
7
        res.push_back(s);
8
    }
9
    sort(res.begin(), res.end());
10
    return res;
11
}

要点：

子集和、最接近目标、计数类问题常用。
一半枚举，一半排序后二分或双指针。

5. 整体二分思想#

整体二分用于多询问第 k 小、动态排名等问题，把答案值域二分并批量处理询问。

要点：

外层二分答案值域。
用数据结构统计左半答案对每个询问的贡献。
贡献足够的询问进入左半，否则修正 k 后进入右半。

常见坑：

整体二分实现复杂，先掌握离线第 k 小模型。
每层递归要撤销数据结构修改或使用临时数组。

训练题型：

静态区间第 k 小。
带修改区间第 k 小。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

分治专题补充#

CDQ 分治#

CDQ 分治常用于离线偏序问题和动态贡献统计。核心是在分治合并阶段计算跨左右区间贡献。

三维偏序：一维排序，一维 CDQ，一维树状数组。
动态逆序对、离线修改查询也常见。
难点是排序稳定性和撤销树状数组。

分治求最近点对#

平面最近点对可用分治做到 $O(n\log n)$ 。

按 x 坐标分成左右。
递归求左右最近距离 d。
只检查中线附近宽度 d 的点。
按 y 排序后每个点只需检查常数个后继。

二分图上二分答案#

“最大值最小”经常二分答案，然后转成判定问题。

判定可能是贪心、BFS、最大流或匹配。
不要把优化问题和判定问题混在一起写。

并行二分#

多个询问共享一批修改时，可以并行二分答案。

每轮把询问按 mid 分桶。
按时间顺序加入修改。
判断询问是否已经满足。
常见于整体离线第几次达到条件。

递归爆栈处理#

OI 中树深可达 $2\times10^5$ ，递归 DFS 可能爆栈。

改写为显式栈。
或在支持的平台调整栈大小。
Python 需要 sys.setrecursionlimit，但仍可能慢。

高频模板训练卡#

这一组训练卡用于把“03_递归_分治_二分”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：整数二分最小可行#

题目信号：答案或结构具有整数二分最小可行特征。
优先模板：套用整数二分最小可行模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道整数二分最小可行题，写出区间语义和正确性证明。

卡 2：整数二分最大可行#

题目信号：答案或结构具有整数二分最大可行特征。
优先模板：套用整数二分最大可行模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道整数二分最大可行题，写出区间语义和正确性证明。

卡 3：浮点二分#

题目信号：答案或结构具有浮点二分特征。
优先模板：套用浮点二分模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道浮点二分题，写出区间语义和正确性证明。

卡 4：三分搜索#

题目信号：答案或结构具有三分搜索特征。
优先模板：套用三分搜索模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道三分搜索题，写出区间语义和正确性证明。

卡 5：归并分治#

题目信号：答案或结构具有归并分治特征。
优先模板：套用归并分治模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道归并分治题，写出区间语义和正确性证明。

卡 6：快速幂#

题目信号：答案或结构具有快速幂特征。
优先模板：套用快速幂模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道快速幂题，写出区间语义和正确性证明。

卡 7：折半搜索#

题目信号：答案或结构具有折半搜索特征。
优先模板：套用折半搜索模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道折半搜索题，写出区间语义和正确性证明。

卡 8：CDQ 分治#

题目信号：答案或结构具有 CDQ 分治特征。
优先模板：套用 CDQ 分治模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道 CDQ 分治题，写出区间语义和正确性证明。

卡 9：整体二分#

题目信号：答案或结构具有整体二分特征。
优先模板：套用整体二分模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道整体二分题，写出区间语义和正确性证明。

卡 10：并行二分#

题目信号：答案或结构具有并行二分特征。
优先模板：套用并行二分模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道并行二分题，写出区间语义和正确性证明。

卡 11：分治最近点对#

题目信号：答案或结构具有分治最近点对特征。
优先模板：套用分治最近点对模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道分治最近点对题，写出区间语义和正确性证明。

卡 12：递归转迭代#

题目信号：答案或结构具有递归转迭代特征。
优先模板：套用递归转迭代模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道递归转迭代题，写出区间语义和正确性证明。

卡 13：二分答案 + 贪心#

题目信号：答案或结构具有二分答案 + 贪心特征。
优先模板：套用二分答案 + 贪心模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道二分答案 + 贪心题，写出区间语义和正确性证明。

卡 14：二分答案 + BFS#

题目信号：答案或结构具有二分答案 + BFS 特征。
优先模板：套用二分答案 + BFS 模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道二分答案 + BFS 题，写出区间语义和正确性证明。

卡 15：二分答案 + 匹配#

题目信号：答案或结构具有二分答案 + 匹配特征。
优先模板：套用二分答案 + 匹配模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道二分答案 + 匹配题，写出区间语义和正确性证明。

卡 16：二分答案 + 网络流#

题目信号：答案或结构具有二分答案 + 网络流特征。
优先模板：套用二分答案 + 网络流模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道二分答案 + 网络流题，写出区间语义和正确性证明。

卡 17：递归边界设计#

题目信号：答案或结构具有递归边界设计特征。
优先模板：套用递归边界设计模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道递归边界设计题，写出区间语义和正确性证明。

卡 18：分治合并贡献#

题目信号：答案或结构具有分治合并贡献特征。
优先模板：套用分治合并贡献模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道分治合并贡献题，写出区间语义和正确性证明。

卡 19：快速选择#

题目信号：答案或结构具有快速选择特征。
优先模板：套用快速选择模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道快速选择题，写出区间语义和正确性证明。

卡 20：分数规划二分#

题目信号：答案或结构具有分数规划二分特征。
优先模板：套用分数规划二分模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道分数规划二分题，写出区间语义和正确性证明。

卡 21：倍增跳跃#

题目信号：答案或结构具有倍增跳跃特征。
优先模板：套用倍增跳跃模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道倍增跳跃题，写出区间语义和正确性证明。

卡 22：指数搜索#

题目信号：答案或结构具有指数搜索特征。
优先模板：套用指数搜索模板，先定义 check 或 merge。
核心不变量：二分保持答案区间不丢失，分治保证子问题覆盖完整。
复杂度目标：二分 O(log V * check)，分治通常 O(n log n)。
不适用场景：check 不单调、函数不单峰、子问题不独立时不适用。
实现检查：检查 mid 取法、边界闭开、递归终止、合并是否漏跨区间贡献。
边界样例：最小答案、最大答案、无解、所有元素相同。
训练题型：找 2 道指数搜索题，写出区间语义和正确性证明。

本章赛前默写任务#

03_递归_分治_二分：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：递归边界#

识别信号：题面出现与“递归边界”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归边界”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：递归栈#

识别信号：题面出现与“递归栈”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归栈”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：归并分治#

识别信号：题面出现与“归并分治”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“归并分治”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：快速幂#

识别信号：题面出现与“快速幂”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速幂”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：快速选择#

识别信号：题面出现与“快速选择”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速选择”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：整数二分#

识别信号：题面出现与“整数二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“整数二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：浮点二分#

识别信号：题面出现与“浮点二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“浮点二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：答案二分#

识别信号：题面出现与“答案二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“答案二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：三分#

识别信号：题面出现与“三分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“三分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：折半搜索#

识别信号：题面出现与“折半搜索”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“折半搜索”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：CDQ 分治#

识别信号：题面出现与“CDQ 分治”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“CDQ 分治”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：整体二分#

识别信号：题面出现与“整体二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“整体二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：并行二分#

识别信号：题面出现与“并行二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“并行二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：分治合并贡献#

识别信号：题面出现与“分治合并贡献”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“分治合并贡献”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：递归改迭代#

识别信号：题面出现与“递归改迭代”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归改迭代”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：递归边界#

识别信号：题面出现与“递归边界”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归边界”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：递归栈#

识别信号：题面出现与“递归栈”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归栈”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：归并分治#

识别信号：题面出现与“归并分治”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“归并分治”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：快速幂#

识别信号：题面出现与“快速幂”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速幂”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：快速选择#

识别信号：题面出现与“快速选择”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速选择”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：整数二分#

识别信号：题面出现与“整数二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“整数二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 22：浮点二分#

识别信号：题面出现与“浮点二分”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“浮点二分”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 3 章 递归、分治与二分#