Book Notes · Contest Track · Entirely Beyond 408

算法竞赛进阶指南
竞赛向路线

定位先说清：本书整体是竞赛向，超出 408 数据结构。408 停在线性表、树、图的基础算法、查找与八大内排。下面每一节都标超纲。紫书当题集；本页当「课内完成之后的路线图」，不把倍增、ST 表、斜率优化默进统考。

倍增 / ST 单调栈队列 DP 优化图论进阶自测

01倍增与 ST 表

竞赛向 / 超出 408预处理倍增祖先、稀疏表 RMQ，统考不要求。

倍增：预计算「走 2^k 步到哪」，把线性跳跃收成对数次。ST 表用于幂等运算（如 min/max）的静态 RMQ：两个可重叠的 2^k 区间覆盖任意询问区间，才能 O(1) 查。加法等非幂等运算不能这样拼。动态修改也不是这份表的工作。

课内对照：BST / AVL 解决的是动态有序集合；这里解决的是静态区间询问。不要把 ST 表写成「另一种平衡树」。

全书 06（课内）全书 08

02单调栈与单调队列

竞赛向 / 超出 408维护候选极值的单调结构，数据结构科目通常不单独命题。

栈里下标对应的值保持单调，用来找「下一个更大 / 更小」。单调队列维护滑动窗口最值时有两条规则：入队时从队尾删去不可能再成为答案的劣值；下标过期时从队首弹出（队列存下标以判过期）。缺这两条算法不成立。课内栈是 LIFO、循环队列判空 front==rear、判满 (rear+1)%M==front——那些定义不改。

全书 03 题型模式专题

03DP 优化概览

竞赛向 / 超出 408单调队列优化、斜率优化、决策单调性。动态规划在 408 数据结构不单列；活动选择等贪心证明也不进必答。

只记一句动机：转移若满足四边形不等式或斜率单调，可以少枚举。不要把「DP 都是 O(n²)」或「优化后都是 O(n)」写成通例。

CLRS · 高级设计超纲

04图论进阶概览

竞赛向 / 超出 408强连通 / 双连通、2-SAT、网络流、差分约束。课内停在 BFS/DFS、非负 Dijkstra、Floyd（负权禁负环）、BF（源点可达负环）、拓扑（仅 DAG）、Prim/Kruskal（无向可负）。

课内遍历 / 最短路 / MST→竞赛：分量 · 流 · 约束

进阶工具不改课内前提：Dijkstra 仍然不能吃负权；Bellman-Ford 仍然只保证源点可达负环。

全书 07 演示 · 最短路

章末自测

不要。它只对幂等运算（min/max）的静态 RMQ：两个可重叠 2^k 区间覆盖询问才 O(1)。加法不能这样拼。408 查有序表用折半。

不改。front==rear 空，(rear+1)%M==front 满（浪费一格）仍是课内定义。单调队列还要：队尾删劣值、队首按下标弹过期。