模板目录

遍历与连通性 · dfs-components

沿邻接关系追到底，回答可达性、连通块数量或每个连通块的聚合信息。重点不是路径有多短，而是把一个区域完整地吃掉。

遍历与连通性 · bfs-components

用 FIFO 队列完整遍历可达区域，稳定处理大图连通性，并为层数、父节点或区域编号保留扩展空间。

遍历与连通性 · grid-flood-fill

把矩阵视为隐式图，从种子格沿方向规则吞并一个极大连通区域，用于染色、计数、边界接触和封闭性分析。

遍历与连通性 · topological-sort

把依赖关系转成可执行顺序；反复移除没有未完成前置项的节点，同时检测有向环，并可扩展为分层执行或 DAG DP。

有序前沿与路径 · bfs-unweighted-shortest

每个动作都计一次，代价完全相同。

有序前沿与路径 · dijkstra-shortest-path

目标是路径上代价、延迟或长度的总和最小。

有序前沿与路径 · zero-one-bfs

动作分成免费与花费一次两类。

有序前沿与路径 · minimax-dijkstra

目标措辞是 minimize the maximum、minimum required threshold 或 bottleneck。

有序前沿与路径 · best-first-boundary-flood

过程从外圈、多源或已知安全边界向内部推进。

二分与单调答案 · binary-search-sorted

利用有序性，每次比较都安全排除一半候选，在排序序列中定位一个确切目标或确认不存在。

二分与单调答案 · binary-search-boundary

在单调布尔序列 F…F T…T 中定位第一个 True，或通过谓词变换得到 last False、lower_bound、upper_bound 等边界。

二分与单调答案 · binary-search-answer

不直接构造最优方案，而是在候选答案 x 上问 can(x)，利用可行性单调性定位最小可行值或最大可行值。

双指针与滑动窗口 · two-pointers-opposite

让左右指针从候选域两端向内夹逼，利用有序性或端点支配关系，每一步安全排除至少一个端点。

双指针与滑动窗口 · two-pointers-same-direction

用 read 扫描输入、write 维护已规范化输出前缀，在原地完成过滤、去重、压缩、稳定搬移或合并。

双指针与滑动窗口 · sliding-window-fixed

对所有长度恰为 k 的连续片段做统计，通过“加入一个、移除一个”增量更新，把每窗 O(k) 降为总计 O(n)。

双指针与滑动窗口 · sliding-window-variable

在连续区间上让右端扩张、左端只向前收缩，增量维护约束，求最长合法窗口或满足条件的最短窗口。

双指针与滑动窗口 · linked-list-rewire

通过保存后继、修改 next 和推进角色指针，在 O(1) 额外空间内完成链表反转、删除、拼接、分段重排或环操作。

前缀、差分与哈希状态 · prefix-sum

对同一静态数组反复查询连续区间和。

前缀、差分与哈希状态 · prefix-state-hash

把连续区间条件改写为“当前前缀与某个历史前缀的关系”，用哈希表在线查找或计数历史状态，从 O(n²) 枚举区间降到 O(n)。

前缀、差分与哈希状态 · difference-array

有大量 range add/subtract，最后才读取结果。

前缀、差分与哈希状态 · frequency-counting

把元素映射到键域并维护出现次数，用计数而非位置表达多重集合，支持相等性、配对、桶排序、投票与频率驱动的重建。

栈、单调栈与单调队列 · stack-state-machine

用 LIFO 栈保存尚未闭合的上下文或可撤销历史，让嵌套解析、表达式求值、路径归约与递归过程显式化。

栈、单调栈与单调队列 · balanced-delimiter-stack

验证或分析多类嵌套定界符，让每个关闭符只与最近尚未匹配且类型对应的开放符配对，并可记录位置、深度或最长合法段。

栈、单调栈与单调队列 · monotonic-stack

维护尚未得到答案的候选索引按值单调排列；新元素一次性解决被它支配的旧候选，用于最近更大/更小、跨度、柱状矩形和贡献计数。

栈、单调栈与单调队列 · monotonic-deque

每个长度 k 窗口都要最大值或最小值。

堆、选择与流 · top-k-heap

只要第 k 大/小或前 k 名，不要求其余元素的全序。

堆、选择与流 · k-way-merge-heap

把多个各自有序的来源合成全局有序流，或只消费全局前若干项。每个来源只暴露一个尚未消费的头部，堆选择这些头部中的最小者。

堆、选择与流 · two-heaps-stream

数据逐项到达，每次插入后查询中位数。

贪心与调度 · interval-sort-greedy

把区间问题变成沿坐标轴的不可逆扫描：按起点或终点排序，维护对未来最有利的边界，解决最大兼容集合、最少删除冲突、合并或覆盖。

贪心与调度 · exchange-order-greedy

推导并证明一种局部次序：相邻决策若违反该次序，交换它们不会让目标变差；于是可逐步把任意最优解改造成贪心排序。它是证明框架，不是‘排序后随便取’。

分治与归并计数 · divide-and-conquer

把规模 n 的问题拆成结构相同、交叠很少的子问题，递归解决，再用受控 combine 恢复跨边界信息。设计中心是‘子调用返回什么摘要’，而不是机械写两次递归。

分治与归并计数 · merge-sort-counting

在归并排序的 combine 阶段利用左右两半已排序，把跨中点的成对关系从逐对检查压缩为双指针批量计数。

分治与归并计数 · quickselect

只求第 k 大/小、中位数或一个排名边界。

动态规划 · linear-dp

沿序列顺序处理前缀，把指数级决策树压缩为少量‘处理到位置 i 时’的状态；每一步只依赖已确定的较早位置。

动态规划 · grid-dp

在移动方向形成 DAG 的网格上，把到达/离开每个格子的最优值或方案数由已完成邻格组合，避免枚举所有路径。

动态规划 · knapsack-dp

每个对象有重量/代价与可选价值。

动态规划 · subsequence-dp

在可跳过元素、保留相对顺序的选择中，用‘以位置结尾’或‘两个前缀之间’的状态表达最长、最少编辑或匹配方案。

动态规划 · interval-dp

子问题由连续区间 [l,r] 唯一描述。

动态规划 · state-machine-dp

每个时刻只能处于少量互斥模式。

动态规划 · tree-dp

在树的无环层级上，让每个节点向父节点返回少量互斥状态；父节点合并独立子树，解决选择约束、路径最值或方案计数。

动态规划 · digit-dp

要求统计 [0,N] 或 [L,R] 内整数。

回溯与约束搜索 · subsets-combinations-backtracking

系统枚举集合选择：用 start 把同一组合限定为一种生成顺序，用 path 表示当前部分解，在进入/退出递归时选择与撤销。

回溯与约束搜索 · permutation-backtracking

逐位置构造有序排列；used/原地交换记录当前路径占用的元素，使每层从所有剩余候选中选择，并对重复值执行同层去重。

回溯与约束搜索 · constraint-backtracking

求一个或全部满足约束的赋值：每次给变量选择值，立即维护局部冲突摘要，失败就撤销；通过变量/值排序与传播尽早剪掉不可能分支。

树、BST 与 Trie · tree-recursive-aggregation

用 postorder 让每个节点先获得子树摘要，再向父节点返回它真正需要的最小信息；同时可在当前节点更新不能整体向上传递的全局答案。

树、BST 与 Trie · tree-level-order

用 FIFO 队列按深度层扩展树；每轮冻结当前 queue 长度，恰好处理一整层，从而输出层统计、视图或最小深度。

树、BST 与 Trie · bst-order-invariant

利用 BST 的全局有序约束：中序产生有序序列，或每个节点继承所有祖先共同确定的值域；据此验证、查找、求秩和前驱后继。

树、BST 与 Trie · trie-prefix-search

把多个字符串的共同前缀物化为共享路径，使插入、完整词查询、前缀查询及前缀驱动 DFS 的剪枝只沿字符深度进行。

并查集、MST 与离线激活 · union-find-connectivity

反复合并两组并查询同组

并查集、MST 与离线激活 · kruskal-mst

连接全部点并最小化总成本

并查集、MST 与离线激活 · offline-activation-dsu

许多不同阈值下的连通查询

区间查询数据结构 · fenwick-tree

点更新与区间查询在线交错

区间查询数据结构 · segment-tree

查询与更新在线交错

区间查询数据结构 · sparse-table

数组构建后不更新

字符串匹配、哈希与回文 · kmp-string-matching

在线性时间查找单个模式串的全部精确出现，并复用已匹配前缀避免文本指针回退。

字符串匹配、哈希与回文 · rolling-hash

大量子串相等比较

字符串匹配、哈希与回文 · palindrome-center

把每个回文唯一归属到中心，通过向两侧扩展统计或寻找最长回文；更大规模时升级为 Manacher。

数学、数论与组合 · gcd-number-theory

要求最大公共单位

数学、数论与组合 · sieve-prime-factorization

需要某范围全部质数

数学、数论与组合 · modular-arithmetic

在大数计数与幂运算中维持同余类，并用平方倍增把指数运算压到对数时间。

数学、数论与组合 · combinatorics-counting

把庞大枚举空间映射为可计数结构，用乘法原理、组合数或容斥直接计算方案数。

位运算与位掩码状态 · bitwise-invariants

逐位独立推理，利用 XOR 消去、位计数或掩码变换压缩整数集合中的奇偶与唯一性信息。

位运算与位掩码状态 · bitmask-enumeration

n 很小且要看所有子集

位运算与位掩码状态 · bitmask-dp

当已选择集合决定未来时，以 mask 作为 DP 状态，复用相同集合的最优子问题。

几何、扫描线、模拟与解析 · geometry-orientation

判断三点方向或共线

几何、扫描线、模拟与解析 · line-sweep-events

区间重叠或并发峰值

几何、扫描线、模拟与解析 · simulation-state-machine

把过程规则翻译为最小充分状态与纯转移，逐步复现行为，并在必要时检测循环或快进。

几何、扫描线、模拟与解析 · parsing-tokenization

用扫描指针与有限状态把原始字符流切成有类型的 token，为表达式、路径或结构化文本建立可靠边界。

几何、扫描线、模拟与解析 · design-data-structure

要求实现一个类或在线 API