题目列表

用双指针枚举答案区间，再用单调队列维护当前窗口内“长度恰好为 d 的子段最大和”，从而快速判断把哪一段清零后能否让总和不超过 p。

设 dp[i] 表示到第 i 棵树的最少疲劳跳跃次数，用单调队列维护最近 k 棵树里“dp 更小且高度更优”的候选前驱，把每次询问做到 O(n)。

把每段固定方向的时间看成一次行或列上的区间转移，设 dp[x][y] 表示当前位置最大滑行距离，再用单调队列优化每段的滑动窗口最大值。

设 dp[i][j] 表示第 i 天结束时持有 j 股的最大收益，把买卖转移改写成区间最值，再用单调队列把每一天优化到 O(MaxP)。

先二分最长段长度的最小可行值，再在该上界下用滑动窗口优化的计数 DP 统计所有合法连续划分方案。

设 dp[i][j] 表示长度为 i、逆序对数为 j 的排列个数，再用插入最大值的转移和前缀和把求和优化到 O(nk)。

把每一行压成二进制状态，预处理单行合法状态后按行做状压 DP，统计所有不相邻的种草方案数。

先预处理单行合法状态，再按行做只依赖前两行的状压 DP，求最多能放多少炮兵。

枚举两只小猪反推出一条合法下凹抛物线，把每条抛物线离散成一个覆盖集合，再做最少集合覆盖的状压 DP。

把较短维压成二进制状态，按行做三行覆盖检查的轮廓 DP，并用 `(总代价, 油库数量)` 做字典序最优。

把每一列压成二进制状态，利用马只会影响前两列的性质，做记录前两列状态和已放马数量的轮廓 DP。

状压 TSP：用 dp[mask][u] 表示已吃集合 mask 且最后停在 u 的最短距离，起点固定、终点不限。

先在“单次飞行不超过 D”的图上跑 Floyd 求任意两村庄间最短可达代价，再在这个距离矩阵上做状压 TSP。

设 dp[mask] 为安排完这些牛后的最优状态，状态记录最少电梯趟数以及该趟数下最后一趟电梯的最小已载重量。

把每包糖果压成一个口味集合 mask，设 dp[mask] 为覆盖这些口味所需的最少包数，做集合覆盖型状压 DP。

把每份披萨看成一个原料子集，直接状压枚举所有 2^N 个子集并检查是否包含冲突对即可。

设 dp[u][0/1/2] 分别表示 u 放塔、被儿子覆盖、等父亲覆盖的最少塔数，用三状态树形 DP 求树上最小支配集。

把完全二叉树的不完整部分压缩成“最后一个叶子到根”的一条路径，预处理满树方案数后沿这条路径自底向上递推。

把路径内部点的贡献化成 deg(u)-1，将答案转成树上最大点权路径和，再在结尾补上两个端点贡献。

设 dp[u][j] 为 u 子树选 j 个黑点的最大收益，把同色点对距离和拆成每条边两侧黑点对与白点对数量乘边权的贡献来转移。

设 dp[u][j][0/1] 表示子树内选 j 个点给大头且 u 是否属于大头的最小代价，按 M=2 与 M>=3 分别判断父子边是否计入答案。

设 dp[u][j] 为在 u 子树中保留 j 条且仍能通过 u 连到根的边的最优收益，合并儿子时做树上分组背包。

先求以 1 为集会点时的总代价和各子树牛数，再用换根公式 dist[v]=dist[u]+(total-2*sub[v])*w 在线性时间求所有答案。

先用并查集缩掉所有 t=2 的相等点，再只保留 t=0 的不同色森林；计数是森林染色，最小和是带点权二分染色。

设 dp[u][c] 表示 u 染成颜色 c 时整棵子树的合法方案数，再把每个儿子所有不同色状态的方案数乘起来。

先做子树内精确距离 DP，再做一次换根，把父亲方向的精确距离贡献传给儿子，最终累加 0..K 层即可。

设 dp[u] 为以 u 为根能得到的最大二叉树高度，把最深孩子放到兄弟链最后，就有转移 dp[u]=儿子数+max(dp[child])。

设 dp[u] 表示必须包含 u 的最优连通块和，自底向上只吸收正贡献子树，就能在线性时间求树上最大连通子图和。

在线段树中同时维护区间 1 的数量和最长连续 0，并用左优先递归把目标区间最靠前的若干个 0 填成 1。

用树链剖分把树上路径拆成若干个 DFS 序区间，再在线段树中同时维护区间和与区间最大值。

把安装与卸载操作转成根到点路径设为 1、子树设为 0，再用树链剖分配合线段树维护区间赋值和区间和。

按右端点升序贪心处理请求，只要整段畜栏最小剩余容量仍大于零就接下，并用线段树维护区间最小值。

把区间按长度排序后做双指针，在线段树上维护当前长度窗口内的最大覆盖次数，找到最小可行长度差。

把每个乘车请求看成区间装载，按终点升序且同终点按起点降序贪心接单，再用线段树维护路段最大占用。

把城市之间的每一段铁路看成一个位置，请求对应区间 `[O,D-1]` 的整体加法，能否接单只取决于这段区间的最大占用是否超过座位数。

一次染色只能填补两个已黑点之间的空隙，因此答案等价于：两端点初始为黑，且每段初始白色空隙都被至少一个活跃操作跨过。

不要把删除操作当成模除法，而要把每次乘法看成一个位置：插入时赋值为乘数，删除时改回 1，用线段树维护全局乘积。

在线段树节点同时维护区间和与区间最小值，区间加时用同一个懒标记同步更新这两个量。

把灯的开关状态看成 0/1 数组，区间翻转时用 `区间长度 - 当前开灯数` 更新节点，再用懒标记维护整段翻转。

把题意翻成区间约束后，核心只剩查询 `(Y,X)` 中间已知年份的最大降雨量，再配合年份是否完整连续做四类判定。

把每个元素看成最终都会被某个不小于它的相邻块吞并一次，它的最优贡献是左右第一个不小于它的值中的较小者，用单调递减栈即可线性求解。

把每个 K 对应的剩余作业看成一个后缀，预处理后缀和与后缀最小值，就能在线性时间内求出删去最小值后的最大平均分。

先把同一坐标上的星星亮度合并，再把题目转成一维数组上固定长度窗口的最大区间和，用前缀和线性扫描即可。

用线段树维护区间最大值；查询时返回区间最大，更新时在单点位置做 `max(原值, 新值)` 的只升不降修改。

按高度从低到高处理平板，并维护每个单位小格当前最高支撑高度；每块平板左右支柱的长度就是当前高度减去对应边缘小格的最高支撑。

用线段树维护区间里空地数与树苗数，把状态分成老树、空地、树苗三类，就能同时处理整段砍树、局部补种和树苗损失统计。

用 defaultdict 建立单词到文章编号列表的倒排索引，并在每篇文章内先去重。

把所有模式串插入字典树，并在每个前缀节点记录经过它的模式串数量；查询串走到终点后的计数就是答案。

把每个值左边更大元素的个数记为 $c[x]$，则做完 $k$ 轮冒泡后的逆序对数就是 $sum(max(c[x]-k,0))$，再用树状数组维护 $c[x]$ 的动态分布。

先找出本来就不必移动的最长严格递增后缀，再用树状数组统计每头前缀奶牛插入有序部分时应后移的步数。

先把所有彩珠按坐标打平成 `(位置, 颜色)` 序列并排序，再用双指针维护覆盖全部颜色的最短区间。

把地板看成容量为 k 的缓存，缺车且地板已满时始终淘汰未来最晚再次被请求的车，再配合下一次出现位置预处理即可得到最优答案。

前 k 轮已经能区分所有 x，当且仅当前缀询问的 lcm 等于 lcm(1..n)，因此答案就是所有必需质数最高幂第一次被覆盖轮次的最大值。

先把四个面的单位三角形按立体共边关系建成度数不超过 3 的图，再做带父边与值域边界的记忆化搜索，分别取当前节点左右子树的最优解。

把树定根后自底向上维护子树向上延伸的最大未截断衰减，若某个儿子子树再经过父边就会达到或超过初始强度，就必须在该儿子处安装放大器。

利用叶子枝长公式 limb(x)=min((d(x,i)+d(x,j)-d(i,j))/2)，递归删去一个叶子并累加其独有边长，最终得到整棵树的总重量。

把所有加密操作按相反顺序依次撤销，其中分别实现栅栏密码、维吉尼亚密码和 QWE 键盘码的逆变换即可还原原文。

把字符串复制成两倍长度后，用最小表示法比较两个候选循环位移并整段淘汰较差起点，在线性时间求出字典序最小表示的起点。

把每种颜色的首末出现位置看成区间，用栈扫描检查区间是否只存在包含关系；最大栈深就是最少轮数。

把平台序列建成最大笛卡尔树，递归计算每个子盆地先灌到根高度、再整体上涨的体积时间，从而求出各平台被淹没时刻。