题目列表

区间存最低价、最高价与区间内最优交易，合并时取左段最优、右段最优、右段最高减左段最低三者最大；线段树与倍增两种实现，单次询问 O(log n)。

把矩形拆成 x=l 加、x=r 减两个事件，按 x 扫描；y 方向用差分 + 树状数组，同 x 先处理事件再回答询问，正好实现半开区间。

对每个卖出时刻只需知道它左边出现过的最低价，扫一遍滚动维护前缀最小值，把 O(n²) 的两两枚举压成 O(n)。

A[i] 全为正数，前缀和严格递增，于是「sum[k] ≤ T」具有二分性：在线解法从位置 0 从大到小试跳 2^i 定位最后一个可行位置，离线解法把询问按 T 排序后双指针右移推进。

矩形加、点查询：把矩形拆成 4 个带符号的二维差分点，用二维树状数组（外层 x、内层 y）求二维前缀和，单次 O(log²)。

利用扩展域并查集维护朋友域与敌人域，实现敌人的敌人是朋友的传递合并，统计不同团伙代表元数量。

带集合大小的并查集：M 合并时把小家族挂到大家族根下并把人数累加到新根，Q 输出 sz[find(a)]，均摊近似线性。

按编号前缀删点后最大连通块不超过 floor(n/2)：删 1..k 等价于只保留后缀，倒序加点用并查集维护集团大小，首个超过 n/2 的集团所在轮次即最小 k，复杂度 O((n+m)log n)。

把亲戚关系看成无向图的连通性，用带路径压缩与按大小合并的并查集合并全部关系，之后每次询问只比较两人的代表元。

在 n×n 点阵上按顺序加边，加边后成圈等价于新边两端已经连通；连通只合并不分裂，用并查集增量维护，第一条两端同块的边就是答案。

搭配关系把云分成连通块，并查集缩点后每个连通块是一件物品，跑 0/1 背包即可。

把连线看成边权为欧氏距离的无向边，用 Floyd 求全源最短路，也可改用 SPFA 或堆优化 Dijkstra 只求单源 s 到 t。

每条边恰好走一次即欧拉路径：最小奇度点出发，贪心走最小邻点，迭代 Hierholzer 求字典序最小的欧拉路径。

层序保证祖先先于子孙：中序区间中层序排名最小的字符就是子树根，递归切分输出先序。

递归分治：按子串区间直接构造 FBI 树并后序输出，根类型由子串含 0/1 情况决定。

先序首字符定根、中序中根的位置切分左右子树，递归求出每棵子树的叶子数即结点长度，再按先序输出「字符 × 长度」。

孩子链表读入建树，没当过儿子的编号即根；中序递归遍历用计数器数访问名次，值等于 x 时输出并停止，O(n) 完成。

把最少结点数看成去重后的前缀个数：单词按字典序排序后每个单词只需与前一单词比最长公共前缀，答案 = 1 + Σ(|w_i| − LCP(w_i, w_{i-1}))。

哈夫曼思想的贪心：每次用小根堆取出最小的两堆合并，n-1 次合并的总体力最小。

DAG 上求 S→T 的必经边：拓扑 DP 统计每点路径条数（mod 1e9+7），边为必经边当且仅当 入段路径数×出段路径数=总路径数，配合最短路树输出方案。

仙人掌最短路：迭代 DFS 找出每个环并缩成方点建圆方树，把根到点的最短路预处理成方树距离，询问时按 LCA 是圆点还是方点分别算，方点情形在环内取两条弧中较短的一条。

Tarjan 求出初始桥并缩成桥树；加边只会消灭树上路径的桥，用并查集跳链缩点，O(N+M+Q) 维护剩余桥数。

二分最少时间；判定时走不到首都的军队在最高可达点建检查点，未被覆盖的根儿子子树再与能到首都的军队按剩余时间贪心匹配。

树上差分把每条路径的 z 类物品拆成端点 +1、LCA 及其父亲 -1，再逆序自底向上做动态开点权值线段树合并，每个节点 O(log) 直接读出计数最大的种类。

度限制最小生成树：缩掉 Park 跑 Kruskal，每块接最便宜公园边，再用剩余车位做「加公园边、删路径最重非公园边」的最优交换。

横向/纵向极大泥段各作二分图一侧，每个泥格在两段间连边，由 König 定理最小木板数 = 最小点覆盖 = 最大匹配，匈牙利算法求解。

同一格子只算一次 ⇒ 格子拆成入点出点，取分弧容量 1 费用 -a、借道弧容量 K 费用 0；跑 K 次 Dijkstra+势能的最小费用最大流取负。

求无向图的点连通度：拆点把点权 1 变成边容量 1、原图的边给无穷容量，枚举所有点对跑最大流取最小割。

把可放置格子按 (r+c) 的奇偶二染色得到二分图，答案即最大独立集 = 未被禁止的格子数 − 最大匹配，用匈牙利增广路求解。

把「两两不可达的最多点数」翻译成 DAG 最小路径点覆盖，先求可达闭包再拆点跑二分图最大匹配，答案 = N - 最大匹配。

把「某座塔的第 k 次发射」当成一个发射位，命中时刻 = 飞行时间 + 射出时刻；二分答案 D 后建二分图，用匈牙利算法判断 M 个入侵者能否各自分到时刻不超过 D 且互不重复的发射位。

把任务看成 A、B 模式之间的边，最小重启次数等于二分图最小点覆盖，由 König 定理化为最大匹配。

每对情侣的仪式是在开头还是结尾二选一，两两冲突只有 4 种组合，建模成 2-SAT；Tarjan 判无解并按分量编号反向赋值输出方案。

把棋盘按行列奇偶黑白染色，骨牌必然跨色，于是每块骨牌对应二分图的一条匹配边，答案即最大匹配数，用 Hopcroft-Karp 在 O(E√V) 内求出。

把每行、每列看作二分图两侧节点，非禁格作为边，車两两不互攻等价于二分图最大匹配。

把每条无向边拆成正反两条有向弧，问题化为求欧拉回路；用链式前向星加迭代版 Hierholzer 一路摘弧、最后翻转记录顺序输出。

求 SCC 并缩点成 DAG：第一问的答案是入度为 0 的分量数，第二问在分量数大于 1 时是入度 0 与出度 0 分量数的较大值，只有一个分量时为 0。

最优比率环是 01 分数规划：二分 mid，把每条边改成 mid·t−f_v（点权挂入边终点），存在比值更大的环等价于新图有负环，SPFA 用 cnt≥n 精确判负环即可。

函数图即基环树森林：挂树自底向上算“牺牲一个孩子”的最小代价，环上枚举环尾状态后线性 DP，整体 O(N)。

合法树形城堡等价于每个房间各自选一个最短路前驱当父亲；Dijkstra 求 D[]，每条紧边只记到距离更远的端点，答案就是各点紧边数之积。

逐条加边维护位图传递闭包：自环位既用于 O(1) 判矛盾，又让每个点的可达点数成为排名，n 个可达数互不相同即全序唯一。

按 Kruskal 合并事件给非树边批量定价：合并大小为 a、b 的两块时产生 a·b−1 条非树边，每条最小合法权值为 w+1，全部累加即为答案。

相邻面值不同的排列计数：按面值剩余张数分档压缩状态记忆化搜索，转移乘上'选牌×插空'，模 2^64 掩码运算。

把最小环拆成“环上最大编号点 k + 一条只经过编号 <k 的受限最短路”，用 Floyd 每轮先探测候选环再并入 k 松弛，O(n³) 并回溯输出方案。

恰好走 N 条边的最短路：把「走一条边」看成 min-plus 矩阵乘法，用快速幂把 N 次接边压到 O(log N) 次矩阵乘法。

一次交易拆成买入价与卖出价两个独立的极值传播：正图从 1 做 min 松弛求路径最低买价，反图从 n 做 max 松弛求路径最高卖价，枚举分割点取差值最大。

村庄排序后最优解每段连续，单段代价由中位数给出，用前缀和 O(1) 计算，再按四边形不等式的决策单调性用分治把逐层转移从 O(PN²) 降到 O(PN log N)。

区间 DP 加上四边形不等式：最优断点单调使断点范围收缩为 [p(i,j-1),p(i+1,j)]，转移降到 O(N²)；再把首尾相接的候选范围拼成长数组，用 numpy 分段取最小。

以奶牛站立的围栏端点作为状态，用线段树区间赋值加单点查询求出正下方最近的围栏，自底向上 O(N log C) 递推最小水平距离。

树形 DP 求树的最小点覆盖：按 BFS 序自底向上递推 f[u][0/1]，每个点选放或不放士兵，保证每条边至少一端被覆盖。

相邻同色木块先压成颜色段，再用「区间 [i,j] + 段 j 右边还要接上几个同色块 k」做区间 DP：段 j 要么不再牵涉区间内别的段，要么与左边的同色段合并。

把聚合看成消去环上的中间标记，用「最后一步把连续段劈成两半」做区间 DP，环拆链复制一倍后对 N 个窗口取最大值。

把均方差化简为最小化平方和后，用「剩余矩形 + 还要切几块」做记忆化 DP，每次枚举一刀割下的那块并让剩下的矩形继续递归。

把折叠串最外层只可能是拼接或重复这一观察落到区间上，用区间 DP 求最短长度，再按决策树还原答案串。

把 SS 串按首原子唯一拆成「原子 + 剩余」，用深度上界态 f[d][i][j][k] 做四维计数 DP，答案由 f[D]-f[D-1] 差分得到。

等分大理石即多重背包可行性：奇偶剪枝排除总价值为奇数，再用 Python 大整数当位集，每块一次 reach |= reach << w 完成转移。

状态只记四类卡片各用了几张：落点 pos=c1+2c2+3c3+4c4 由四元组唯一确定，dp 从四个前驱取 max 再加当前格分；实现上把 c4 压成 accumulate 前缀链、c1 维滚动，O(∏(c_k+1))。

线性 DP：dp[i][j] 表示第 i 朵花放花瓶 j 的最大美观值，前缀最大值 O(FV) 转移，再用后缀 DP + 贪心还原字典序最小的摆放方案。

把每个性格值剥掉立方因子得到立方核，乘积为完全立方等价于两核互补；冲突退化为互补核配对，逐对取人数多的一侧、核 1 只留 1 人。

交错条件只比较相邻两块的高低，把剩余板按大小重编号即可压出 (剩余块数,当前名次,角色) 的计数状态；递推后逐位试填，整块跳过定位字典序第 C 个排列。