# 课程使用说明：把例题读成一节课

## 本节目标

读完后，你应能选择适合自己的阅读路线，知道每个折叠区何时展开，并能在不提交每一道课内题的情况下提炼可迁移的算法能力。

## 前置知识与课前自测

前置只需要 C++ 基础、常见 STL 和基础复杂度分析。先回答：

1. 看到 $n=2\times 10^5$，为什么通常要先排除 $O(n^2)$？“常数小”能否挽救它？
2. 一份题解说“用 Tarjan”时，你还需要追问哪些正确性和实现问题？
3. 如果读懂了代码却说不出算法在什么条件下失效，算不算掌握？

<details>
<summary>展开自测参考</summary>

1. $O(n^2)$ 约为 $4\times 10^{10}$ 次基本操作，远超常规时限；只有证明实际访问量更小，才可改变判断。
2. 至少要问：维护什么状态和不变量、何时入栈/出栈、边的分类、重边与自环、递归深度、复杂度。
3. 不算。能说明适用条件、最小反例和替代方案，才说明掌握的是模型而不是代码形状。

</details>

## 先吃一份课前零食

每个算法大主题的首篇正式课前都有一篇 `00-课前零食`。它面向已会 C++、STL、基础 DFS/BFS 的普及+同学，建议在正式课前约一周完成。零食课不用 OJ 例题：它会从最暴力结构或做法出发，用贯穿小例、SVG 图示、停顿问题和类 Python 伪代码推到算法为什么出现。

每篇还链接一份位于根目录 `互动程序/` 的 Python 3 终端小实验室。无需安装第三方库；直接按文档中的命令运行，按回车可使用预设数据。它的任务是让你观察状态变化和不变量，不是让你背一段可提交代码。

若读正式课时发现某个名词像空中楼阁，优先回到对应主题的零食课，而不是硬着头皮往下翻。

圆方树、Kruskal 重构树、Splay、文艺平衡树和 ODT 的思维跨度更大，课程索引还安排了它们各自的专项零食。它们不是重复定义：会分别从“块怎样重叠”“DSU 忘了什么”“旋转保住什么”“位置怎样取代值”“段数为何可能失控”起步。

### 零食课的互动协议

零食课不是“读到算法名，再点开答案”的缩短版讲义。请准备一张纸，按下面四栏工作；每一轮都先写，再展开折叠区或运行程序。

| 纸上栏位 | 要写什么 | 它防止什么 |
|---|---|---|
| 对象 | 此刻正在处理哪些点、边、字符、区间或数？ | 一开始就被术语带跑 |
| 状态 | 为了继续做下一步，当前必须记住什么？ | 只会背数组名，不懂数组意义 |
| 动作 | 本轮允许做哪一步？会改变哪些状态？ | 把算法看成不可解释的黑箱 |
| 账本 | 哪些工作重复了、哪条性质必须一直成立？ | 只知道“快了”，不知道为什么 |

每个零食课至少经过四步：

1. **先当人脑暴力程序。**按题中小数据一步一步做，并把每一次比较、搬动、回退或枚举记下来。
2. **让暴力法真的撞墙。**不是接受“它很慢”，而是指出哪个状态被重复算、哪种选择会走死、哪一项信息丢了。
3. **只发明一个新部件。**例如一个摘要、一条边界、一份颜色、一棵局部树；写清它存什么、何时更新、它替你省掉什么。
4. **再让程序当验算员。**先预测下一行日志，再按回车查看；预测错了也不是失败，而是找出自己漏掉的状态。

程序若要输入命令，先把“我预测会发生什么”写成一句话。例如：`sum 2 5` 前写下你认为 Fenwick 会拿哪几块；`+ 6` 前画出 Treap 的键值左右关系。读懂输出不等于完成，能在输出前预测才算搭起框架。

## 两条阅读路线

### 尝试路线

适合有完整训练时间时：读题后先只看 Hint 1；卡住 15–25 分钟再逐级展开。写完后必须对照 Editorial 的观察链和证明，而不是只检查代码是否相似。

### 直接学习路线

适合“今天不做这题，但要获得尽可能大收益”时。每道课内题按下面顺序读：

1. **约束翻译**：先把数据范围变成可接受复杂度候选。
2. **模型信号**：圈出决定建模的动词、对象和不变量。
3. **错误路线**：看一个最小反例，明确常见直觉错在哪里。
4. **Observations**：逐条确认每个观察究竟删掉了哪些状态或转移。
5. **Editorial 与证明**：先复述算法，再检查合法性、完备性和终止结论。
6. **代码走读**：给每个数组写一句语义；模拟一个正常样例和一个边界样例。
7. **反事实变化**：修改一个条件，判断原算法哪里先失效。

这条路线不要求提交，但要求留下三行复盘：识别信号、核心不变量、最容易写错的一行。

## 例题在课程中的分工

- **模型建立题**：通常为 CodeForces 1600–2000 或等价难度，负责把定义变成算法。
- **组合迁移题**：通常为 CodeForces 2000–2500，要求把本节技巧与已有工具组合。
- **灵活性实验室**：全课程每 2–3 个大主题安排一道，允许达到 2800+，也允许只与当前主题部分相关；重点是构造、交互、反向思考或异常建模，不作为后续课程的硬前置。
- **课后训练题**：用于独立提交。若没有完整 Editorial，就不会冒充正式例题。

## 正式例题的阅读结构

从本批课程起，正式例题不在正文铺开完整 C++。每题按以下顺序组织：

1. **Observations**：至少说明数据范围排除了什么、朴素路线卡在哪里、哪条新观察真正改变状态数或复杂度。
2. **Editorial**：从对象与关系的建模开始，逐步推出算法；不能用“套模板”替代推导。
3. **正确性证明**：分别证明每步合法、不会漏解/重复、终止答案达到目标；最优化题还要写出下界或交换论证。
4. **复杂度与适用边界**：把复杂度代回本题范围，并给出至少一个去掉关键条件后会失效的情形。
5. **类 Python 核心伪代码**：只保留决定算法结构的状态和转移，隐藏 C++ 容器噪声。
6. **参考实现附件**：完整 GNU C++17 放在仓库根目录 `参考实现/`，讲义用链接引用；附件仍参与统一编译和测试。

若只阅读不提交，至少应能在看附件前根据伪代码复述完整数据流。

## 如何使用 Hint

每级 Hint 必须改变你能做的事：

- Hint 1 只指出模型识别方向；
- Hint 2 给出关键性质，但保留算法组织；
- Hint 3 给出算法骨架；
- Hint 4 才触及实现中的下标、状态或边界。

若相邻两级只是换句话说，应视为文档质量问题。

## 代码、测试与评测声明

所有参考实现以 GNU C++17 为准。课程中的“已验证”分为三层：

本查看器中的多行展示公式统一使用独占行的双美元符号作为起止定界符。

1. **编译验证**：通过 `-Wall -Wextra`，只说明语法、类型和链接成立。
2. **本地行为验证**：通过来源样例或随机对拍，说明覆盖范围内的行为一致。
3. **在线评测**：只有确实提交并获得记录时才会声明；本课程默认不虚构此层。

交互题没有普通标准输入输出。课程会提供最小模拟器检查协议、查询次数与答案恢复，但这仍不等价于原平台在线通过。

## 总结与自检

完成任一章节后，尝试脱离文档回答：

1. 这个算法解决的瓶颈是什么？
2. 它依赖的关键条件是什么？去掉该条件的最小反例是什么？
3. 正确性证明的核心不变量是什么？
4. 数据范围为何允许该复杂度？
5. 如果明天忘了模板，能否从定义重新推导出主要步骤？

## 课后训练建议

模型建立题建议独立实现；组合迁移题至少口述完整算法后再看代码；灵活性题先画状态或构造小例，30 分钟没有新观察再展开下一层 Hint。复盘时优先记录“我为何没识别出来”，而不是抄一遍模板。