竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1单调栈与最近更大元素

闭卷重建单调栈与最近更大元素的对象、状态、事件、不变量与一个失败反例。

2单调队列与区间最值

闭卷重建单调队列与区间最值的对象、状态、事件、不变量与一个失败反例。

3堆与动态Top-K

闭卷重建堆与动态Top-K的对象、状态、事件、不变量与一个失败反例。

4并查集与连通分量

闭卷重建并查集与连通分量的对象、状态、事件、不变量与一个失败反例。

5树状数组的低位分解

闭卷重建树状数组的低位分解的对象、状态、事件、不变量与一个失败反例。

6线段树的区间合并

闭卷重建线段树的区间合并的对象、状态、事件、不变量与一个失败反例。

7可持久化思想入口

闭卷重建可持久化思想入口的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕单调队列与区间最值先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成单调队列与区间最值的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕单调栈与最近更大元素先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成单调栈与最近更大元素的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕并查集与连通分量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成并查集与连通分量的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕堆与动态Top-K先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成堆与动态Top-K的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕线段树的区间合并先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成线段树的区间合并的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕树状数组的低位分解先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成树状数组的低位分解的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕可持久化思想入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成可持久化思想入口的暴力、优化、对拍与复盘；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。本课必须再检查边界输入、整数溢出、下标和不可行状态。。