题目列表

dummy 头结点，每次接入较小节点，最后接剩余链。

滑动窗口维护 need/have 计数，右端扩张满足需求，左端收缩到刚好不满足，O(n)。

快慢指针找中点，反转后半段，与前半段比较，O(n) O(1)。

结果先存左侧前缀积，再乘右侧后缀积，O(n) 时间 O(1) 额外空间。

dummy + 快慢指针相距 n+1，快指针到尾时慢指针在待删节点前一位。

prev/cur/next 三指针逐节点反转，同时保留后续节点引用。

先找第 k 个节点，翻转这一段并接回；不足 k 段保持原样。

三次反转：整体反转，再分别反转前 k 和后 n-k；先取 k %= n。

先沿主对角线转置，再逐行反转；原地旋转 90 度顺时针，O(n²) O(1)。

从右上角出发，小于 target 向下，大于 target 向左，每步排除一行或一列，O(m+n)。

用首行/首列充当标记位，先记录首行首列是否含零，再标记并回填，O(1) 额外空间。

单调递减队列保存候选下标，过期从队首删，较小候选从队尾删，O(n)。

快慢指针拆半，递归归并排序，O(n log n) 时间 O(log n) 递归空间。

维护 top/bottom/left/right 四条边，按右/下/左/上收缩并检查边界，避免单行/单列重复。

前缀和 + 哈希表统计历史前缀出现次数，边扫边累计答案，O(n)。

dummy + prev/a/b/next 四指针每轮重连已交换段和待处理段。

定义 mirror(a,b)：值相等且 a.left 对 b.right、a.right 对 b.left。

双指针维护左右最高柱，较矮侧水量可立即确定，O(n) 时间 O(1) 空间。

排序后固定第一个数，剩余区间用双指针，跳过相同值去重，O(n²)。

双指针维护区间，面积由短板决定，每次移动较矮一侧，O(n)。

双指针：write 指针收集非零元素，剩余补零，保持非零相对顺序。

放入集合，只从 x-1 不存在的起点向后扩展，每个数至多被访问一次，均摊 O(n)。

为每个单词构造 26 字母计数 key，哈希到同一组；异位词一定有相同的字母构成。

遍历数组时用哈希表保存值到下标的映射，在线查找当前数所需的补数。

用按高度滚动的动态规划合并连续点击与重力转移，并在管道位置过滤非法高度。

用 Python 整数位集加速 Warshall 传递闭包。

对十个数字求变换传递闭包，再把每一位的可达数字数相乘。

在有向图上同时传播路径最低买价和最大已获利润。

按时间增量加入 Floyd 中间点，在线回答当前已重建村庄间最短路。

BFS 分层并在最短层边上累加方案数，支持重边。

二分允许的最高城市收费，用受限 Dijkstra 检查血量能否到达终点。

对配方超边做 Dijkstra 式松弛，再按最小成本递增顺序统计最优方案数。

把三类作物数量关系统一成差分约束边，并检测负环。

Floyd 同时维护最短距离和路径数，再按经过节点的路径比例计算重要度。

用位集传递闭包统计每头牛已知强于和弱于的数量。

Dijkstra 同时维护每点严格不同的最短与次短距离。

Floyd 预处理岛屿两两最短危险值，再累加指定访问序列相邻项。

把下界约束建成 0/1 边，SCC 判严格环后在缩点 DAG 上求最长路。

从节点 1 运行 SPFA，以最短路边数达到 n 判断可达负环。

以最小步长为模建立余数图，Dijkstra 求每类余数最早可达楼层。

把免费次数作为分层状态，在 n(k+1) 个状态上运行 Dijkstra。

用 heapq 实现带过期状态判断的 Dijkstra，求非负权有向图单源最短路。

把 x_c-x_c'<=y 转成 c' 到 c 的边，用最短路构造可行解。

Floyd 后枚举传送门端点，逐点对比较原路和两个传送方向。

先求树的直径，在直径上用双指针枚举长度不超过 s 的核区间，偏心距由两端距离与分支最大深度决定。

对每个中间点聚合邻居权值，用 S²−Σw² 得到距离为 2 的有序点对总和，用前两大权值求最大值。

把观察条件改写为深度等式，按 LCA 拆两段路径，用桶与树上差分在 DFS 中统计每个观察员看到的人数。

任选根 DFS 求每棵子树大小，边费用 = 边权 × |2·子树大小 − n|，一次遍历累加总费用。

二分答案，倍增 LCA 求路径长度，树上差分找所有超标路径的公共边并比较最大公共边权。

用树链剖分把子树与根路径映射成数组区间，双树状数组维护区间加与区间和，根路径和 O(log^2 n)。

树链剖分把路径拆成区间，按宗教拆成多棵动态开点线段树，只统计同宗教城市的评级和与最大值。

两条树上路径相交当且仅当某条路径的 LCA 落在另一条路径上，用距离等式 dist(u,x)+dist(x,v)=dist(u,v) 判断点在路径上。

重链剖分把祖先路径拆成 O(log n) 段连续区间，线段树维护段内最大已标记 dfn，逐链向上查询最近标记祖先。

用树链剖分把根到节点的路径拆成重链段，线段树维护段内黑点最小 dfn，从根侧逐段查询得第一个黑点。

最坏时间 = min(到两朋友距离) + 两朋友距离；A、B 取直径端点，三次 BFS 后 O(n) 扫描答案。

拓扑剥叶给每个节点分层，选层号最大的 k 个连通节点作核心，答案即第 k+1 大的层号。

根路径 G 前缀和配合倍增 LCA 容斥，O(log n) 回答路径上是否出现指定品种。

离线压缩坐标，外层线段树寻找最左可行 x，组内 Fenwick 找最小可行 y。

Luogu 无法提交 Codeforces 原题，解析已迁移至 codeforces/19D，本页仅保留入口。

用线段树双懒标记维护区间赋值与区间加，赋值覆盖加法、下传先赋值后加，查询区间最大值 O(log n)。