题目列表

用“恰好出现 t 次的颜色种数”把子树判定降到 O(1)，再用 DSU on Tree 让父亲复用重儿子的统计，做到 O(n log n)。

子段异或和化为两个前缀异或的异或，再按位统计前缀异或中 0/1 的个数，用 cnt0×cnt1 累加每位贡献。

把“水往低处流”看成有向图的可达性，每个蓄水厂一次 BFS 求出它能灌溉的干旱区城市；可行时这个集合恰好是一段连续区间，于是问题化为区间覆盖贪心。

$x=y^2-z^2$ 等价于 $x$ 有同奇偶的因子对，即 $x$ 为奇数或 $4$ 的倍数；用前缀计数 $F(R)-F(L-1)$ 即可 $O(1)$ 求出答案。

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

以厘米为整数单位二分长度，用可切出的段数判断可行性。

二分最短跳跃距离，用贪心扫描统计必须移走的石头数。

二分木材长度，统计总共能切出的段数是否至少达到 k。

二分最短跳跃距离，贪心统计给定距离下最少需要移走的石头数。

所有同学等车时间之和最小：以发车时刻为状态 DP，发车时刻闭包剪枝 + 前缀和算等待量，凸壳优化非被迫转移，O(n log n)。

挖遍所有宝藏屋的最小开发代价：枚举生成树的根分层结构，状压 DP f[S] 表示已开发集合的最小代价，预处理子集连接边权和加速转移，O(3^n·n)。

动态出队/补位的行列队列查询：每行与末列各维护一个虚拟队列，离队位置少时平表二分、多时换 Fenwick 树动态查第 k 个在队者，均摊 O(m log n)。

每个数至少有 k-1 个相同数：排序后连续分段 DP（段长≥k），转移化为直线族取 max 用单调队列维护上凸壳，斜率优化 O(n)。

把极大极小乘积按 B 区间符号分三类讨论，只需在 A 区间查询最值、最小正数、最大负数和是否有零。

按开始时间排序后，用小根堆维护每个牛棚最后占用的结束时间；堆顶能空出就复用，否则新开棚，得到最少牛棚数与一套合法分配。

两条航道交叉等价于两岸坐标的顺序相反；把友好城市按南岸坐标排序后，问题变成求北岸坐标序列的最长严格上升子序列，用二分手写 LIS 做到 O(N log N)。

两个排列的 LCS：把 P1 的值映射成它在 P1 中的下标，P2 就变成位置序列，公共子序列恰好对应它的严格上升子序列，再用 tail 数组加手写二分求 LIS，总复杂度 O(n log n)。

前缀 DP：f(i,j) 表示两个前缀的 LCS 长度，字符相等时取 f(i-1,j-1)+1，否则取上侧与左侧的较大值，答案是 f(n,m)。

将连续用户压缩成可动态撕裂的区间块，本质是区间映射: 每次撕裂出一个单点

把被摧毁的房子看成断点，用有序集合维护断点，查询时求左右最近断点使答案等于 R - L - 1；给出 FHQ-Treap 与 std::set 两种实现。

用隐式 Splay 或隐式 FHQ-Treap 维护序列顺序，通过双哨兵或按排名分裂实现区间翻转。

使用01背包DP，dp[c]表示容量c时的最大总价值，容量倒序枚举确保每件物品只选一次；同模型的 Python 写法因 3 MB 内存限制必然 MLE。

比较 n、n^2 与 5×10^8 的关系，按复杂度从高到低输出能够通过的最高级别。

利用兑换门槛不超过 20，把可达钱数拆成低状态和统一平移的高状态，特殊机器再合并至多三份集合。

每次合并当前最小的两堆果子，等价于构造 Huffman 树；可用小根堆维护，也可排序后用两个普通队列 O(n) 完成合并阶段。

DFS 回溯枚举所有简单路径，按 上左下右 方向序输出全部路线，无路输出 -1。

用倍增表 up[u][j] 记录 2^j 级祖先，查询时先提深再同步跳，单次询问 O(log n)。

递归解析方括号结构，遇到 [D... ] 时先展开内部字符串，再重复 D 次拼接。

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

先解决固定根下的活动串贪心，再用分支定向、历史事件归档和共享模拟在线淘汰候选根。

把余额 DP 维护成离散凸函数，用斜率堆完成拉格朗日最优化并二分可行题数。

在二进制 Trie 上递归计算异或阈值冲突图的最大团，并缓存跨子 Trie 状态支持合并。

利用 f(n) 的逐位公式，把区间数位平移转化为线段树上的模 k 线性维护。

用值域计数数组统计每个数的出现次数，再按数值升序选择最高频数。

扫描 ISBN 的前九个数字计算带权和，再按模 11 规则校验或替换识别码。

把 0/1 与 2/3 的先后限制各压缩为三态，用 9 状态 DP 统计合法数字串。

把方向受限地图建成有向图，分别从 S 正向搜索和从 T 在反图搜索，再统计可达集合差集。

用偏移量数组记录已出现整数，读到 x 时查询相反数 -x 是否存在。

扫描命中点击点的窗口并选择最高层，用递增层次编号模拟被选窗口置顶。

预处理每个选项是否带参数，按字符串顺序模拟解析并记录最后一次合法参数。

把新增路由器数量作为 BFS 状态维度，在节点与资源使用量的状态图上求最短路径。

排序后检查相邻元素是否相差 1，直接统计所有满足条件的数对。

把矩形覆盖的单位网格标记为已涂色，最后统计布尔网格中的真值数量。

按大小写选项统一字符串后，用子串查找逐行筛选包含模式串的文本。

用行轮廓 DP 枚举 L 型三格骨牌转移，再对宽度至多 7 的状态矩阵做快速幂。

按记录顺序维护每个读者编号的出现次数，并输出当前记录的累计次数。

按副对角线 i+j 分组，并根据对角线编号奇偶交替反向输出。

用整数分维护有效订单，按报价扫描买单后缀量和卖单前缀量，取最大成交量的最高价格。

把城市-日期拆成时间扩展网络，用最小费用最大流同时决定运输路线和跨日库存。

按原矩阵从右到左的列顺序逐列输出，完成逆时针旋转 90 度。

统计每个数的出现次数，再按频次降序、数值升序排序输出。

顺推每年元旦的星期，利用月初星期和模 7 公式定位第几个指定星期。

重链剖分路径后，用方向敏感的价格前缀最小值分段计算每段行走成本。

线性扫描数列，每次相邻数字变化时计入一个新的连续段。

按闰年规则确定二月天数，再依次扣除每月天数定位日期。

扫描模板中的 {{ VAR }} 标记，用变量表中的值做一次非递归替换。

用 Tarjan 分解强连通分量，分量内任意两城都构成便利城市对。

反复取十进制末位并除以 10，累加所有数位。

在原棋盘上分别标记横竖连续三个以上的同色段，再同时清除。

检查固定起点的欧拉路条件后，按邻接点升序执行 Hierholzer 构造字典序最小路径。