算法 trick 的记录。
系列前作：https://www.luogu.com.cn/article/yc9w22em
拆贡献！拆贡献！交换维度！交换维度！时间逆流！时间逆流！操作顺序反演！操作顺序反演！递推！递推！分离常量！分离常量！不同的项分开算！
优化一些代数式计算的复杂度时，最简单常用的技巧就是试着拆开，然后分离常量和变量，将不同类项分开处理。而当你推不出一些式子时，可以放弃推式子而使用递推。交换求和顺序/交换 DP 转移顺序/维度是破解循环依赖，找到好的计算顺序的方法，这和拆贡献是相关的：拆贡献其实就是变换了统计的第一维度。从按照整体的统计变成按照单个元素统计。
双指针就是“在不合法和不优之间的境界线上游走”，同时也是“一种扫描线”，并且是“在复杂度允许的情况下，枚举一定量信息以确定更多条件”的体现。
而“枚举一定量信息”在 DP 中也很常用。DP 的经典套路就是随便乱设状态，加入信息直到能够转移为止，然后利用种种洞察和优化去掉一部分维度，优化转移直到时空复杂度达标。
在做任何题的时候，第一步考虑性质刻画。无论是操作的性质还是维护信息的性质。性质就是限制，能够帮你找出正解。
一个好的性质刻画也很重要。一个愚蠢的性质刻画会极大地妨碍你做题。所以如果你觉得性质刻画太笨，就试着简化。
“信息学”的本质就是对于信息的处理。算法对于复杂度的优化本质上是减少不必要的对信息的处理（计算）。所以当你试图确定复杂度或者优化复杂度时，不妨思考一下“这个题，至少需要处理哪些信息？如何避免处理不必要的信息？”
信息即向量，操作即矩阵。
写了线性代数大学习，你应当能知道这点。有许多操作都是线性/仿射的，可以写成矩阵。从而拥有结合性，可以用快速幂或者线段树等方法处理。
孤链压缩权值线段树/01 trie。线性空间复杂度，从此整数可重集再也不用平衡树。
线性筛线性预处理积性数论函数。要点在于筛 n = i * p 时用到的 p 和 i 满足 p 不大于 i 的最小质因子。比埃筛更好写。
以后再也不要 naive 地 $O(n \log n)$ 算 d(i) 了。
利用单调性等等贪心性质简化问题。
有交不优 => 钦定末尾。
有时二维问题按第一维排序，而后第二维更小就一定更优所以无脑排除一些。剩下的就满足二维偏序（相当于利用贪心性质额外制造了一个维度上的单调性。这里的贪心性质是“a 被 b 包含 => b 的所有解都不劣于 a 的对应解/a 能干的所有 b 都能干”）
两种证明贪心的策略：
- 局部上，交换论证/调整法：调整一定能导出不劣的解。
- 整体上，必要性 => 充分性：我们至少需要多少操作，然后让这些操作发挥最大的效益。
增量更新并不要求旧的答案一定是新的答案。在旧答案总数很小时，可以暴力枚举它们判断它们是否是新的答案。或者，如果容易确定哪些不是新的答案，排除它们即可。
对于一些非常复杂的操作，可以考虑寻找不变量。常见的不变量常常和奇偶性或者两类元素的差有关。因为总和是容易变的，但是有时对于两类东西的作用是相同的，就可以被作差消去。
当操作是对两个相邻元素（或者类似的，一个元素附近的几个元素）时，这样的关于奇偶性或者奇偶下标的元素的差的不变量比较容易出现。
不变量和另一种思想紧密相关，即状态而非过程。在很多贪心或者博弈论的题中，常常有复杂的流程模拟，直接陷进去就做不出来了。
这时可以考虑最终状态或者解的性质，有时能够得到非常简洁优雅的结果。就像解方程一样。
一些看似具有对称性的问题/贪心策略，其实是不对称的。
这种不对称常常是因为一些题目操作的性质引起的，比如说字典序的比较是从前往后的，这就导致有时你必须逆向贪心。或者一个操作操作了“从当前位置开始，长度为 k 的区间”，这也是一种不对称性，常常导致你需要逆向贪心。
多源 bfs 或 dijkstra/01 bfs 是求出一个点到一组关键点的距离的利器。
来自 CSP-S 2025 的教训：记得测试极限数据。记得检查大样例强度。仔细查看题面，不要想当然由于 t1!=t2 以为 s1!=s2 等等。记得数组不要开小，想清楚数组要有多大。有时本地的越界等会因为神秘原因而不 re，这时使用 sanitizer 是好的。
在对“本质不同的 (x, y) 有序对”计数时，常常考虑枚举 x（或者类似的枚举一维）。但是在对本质不同的 x（单个元素）计数时，这样的做法就行不通了。
常用的方法是把每个元素都映射到一种能够体现它本质的构型上，满足以下几个条件：
- 相同元素映射到相同构型
- 不同元素映射到不同构型
- 构型易于处理，容易进行相等性比较/排序/去重等。
性质刻画有时不要魔怔。你可能会发现刻画走进了死胡同，但是某些力大砖飞的做法反而可行。那么不管什么做法只要能通过就行。
以上两点有例题 CF1849C。
边点互化是图论建模的经典方法。我已经因为不会这个吃了很多亏了。
陷阱：我们一般情况下容易陷入思维定势，认为“物品”一定是点，而“关系”一定是边。但是，边的本质特征是只与两个点有关。所以如果关系是多元的（与多个物品有关）而物品的性质反而是二元的，那么应该考虑边点互化。
例题：电阻网络求解。ABC434E。
bitset 优化高维偏序是一种常用技巧。具体而言，高维偏序是若干一维偏序的逻辑与，也即交集关系。bitset 优化求交集即可。
在面对区间操作时，我们常常利用差分将其转化为单点操作。然而有时，相反的转化（即考虑前缀和）也是有效的。例题：CF1775E。
将排列对应的置换分解为轮换是常用的技巧。
与之配套的有函数图的经典结论：
我们知道交换一个环上的两个点可以将环分裂，交换不同环的点会将两个环合并到一起。
证明：
考虑 $i, j$ 是同一个环上的两个点。设前驱分别为 $v_i, v_j$。交换 $i$ 和 $j$ 本质上相当于让 $v_i$ 指向 $j$ 而 $v_j$ 指向 $i$。
那么，就变成了 $v_i \to j \to p_j \to \dots$，注意到原本这也是一个环，也就是说那串省略号最后会绕回 $v_i$，这就成了一个环。而另一边同理，并且你会发现两个环没有交集。
对于 $i$ 与 $j$ 不在同一个环上的情形，那串省略号不再通向 $v_i$，而是通向 $v_j$，又从 $v_j$ 绕到 $i$，所以两个环就并成了一个。
这里涉及到曼哈顿距离与切比雪夫距离互化的经典 trick。
公式：
$$(x, y) \rightarrow (x+y, x-y)$$这个变换后，原图中的曼哈顿距离就变为切比雪夫距离。
逆变换：
$$(x, y) \rightarrow (\frac{x+y}{2}, \frac{x-y}{2})$$可以将切比雪夫距离转为曼哈顿距离。
为了避免小数，在处理后者时常常将坐标放大二倍。
两个变换的原理是 $|x| = \max(x, -x)$。
这个 trick 的作用在于，将加法和 max 两种操作互相转化。在例题 ABC437F 中，我们需要处理外层是 max，内层是加法的区间查询，直接做需要带修莫队或者复杂的多层树套树/高维偏序。利用曼哈顿距离转切比雪夫距离，我们得以将问题转化为只与 max 有关的区间查询，从而拥有结合性，能够利用线段树简单维护。
这个 trick 之前也偶然见过，不过在场上却没能追忆起来，而是陷入了带修莫队（不会）和高维树套树的死胡同里……警钟长鸣。
背包合并是一个有用的技巧。注意它的复杂度是 $O(V^2)$，但在背包仅处理计数/可行性而不是最大值时能够直接使用 FFT/NTT 做到 $O(V \log V)$。
背包合并可以用于背包的区间查询等。可以用线段树或猫树（二区间合并）维护（背包合并证明背包具有结合律）。
例题：ABC426G
有时我们不需要算出完整的背包，只需要一些特征信息。这时可能可以做到 $O(V \log V)$ 或 $O(V)$。
例题：ARC070B
对于上面那道题，退背包是更简单的做法。退背包即计数类型背包的撤销/删除操作。具体而言，01 背包是从小到大枚举体积然后差分。完全背包则是从大到小枚举体积并差分。
遇到差的绝对值相关的东西，考虑建模为数轴上两点的距离。
一类特殊的拆贡献：对于交换序列上任意一对元素的操作，考虑枚举每两个相邻位置间的那条“缝隙/分界线”，计算有多少必要的交换经过它（即有哪些元素必然从左侧或右侧穿过这条分界线）。
对于交换序列中一对相邻元素的操作，考虑逆序对。
01 背包以及其他 dp 的转移，要记得该继承的时候要继承。
尤其是 01 背包的原始的不带降维的写法，不能从 cost[i] 开始枚举转移，否则小于它的状态就没有继承之前的结果。
https://www.luogu.com.cn/article/dg8kf3f2
用一个集合存储块内所有元素的取值的多重集。
这样的分块思路还是比较常用的。比如 ABC441G。
非常恶心的一个题。极角排序板子。
注意用一个点到原点的连线的斜率会导致 $(x, y)$ 和 $(-x, -y)$ 无法区分。
所以需要按 $x$ 的正负性分类讨论。
另外，注意 $x=0$ 时斜率不存在。而这时也需要注意 $y$ 的正负性：本题中需要区分，但某些题中不应该区分。
有 atan2l 这个函数可以避免手动分类讨论。
atan 是单增的。所以直接用斜率而不是极角的数值会有更好的数值稳定性。
更优秀，完全不需要考虑精度误差的方法是按象限分类之后用叉积。即，对于第一象限内的点 $P_1 = (x_1, y_1)$ 和 $P2 = (x_2, y_2)$，前者的极角大于后者当且仅当 $y_1x_2 > y_2x_1$。
std::lower_bound 和 ranges::lower_bound 传入的比较器 cmp 会被以 cmp(*it, val) 的形式调用，其中 val 是传入的搜索目标值，*it 是序列容器中的值。取第一个表达式返回 false 的迭代器。
upper_bound 刚好相反。cmp(val, *it) 并取第一个表达式返回 true 的迭代器。
关于 tarjan：千万不要误以为无向图上可能有横叉边 ;) 其实只有有向图做 scc 才会遇到横叉边。
另外，做 v-BCC（点双）缩点时，弹栈必须弹到子树根节点而不是当前的 u 节点。因为 u 可能有 v 和 w 两个子树，w 有返祖边而 v 没有。如果先遍历 w 再遍历 v，然后对 v 的 v-BCC 弹栈时一直弹到 u，就会把 w 算进去。
错解不优性质太重要了。或者更加一般的，有时一些状态不合法，但不额外去除它们不会影响答案，因为它们一定比合法状态中的最优解劣。
或者有时一些状态合法，但去掉它们（不考虑它们）也不影响答案，因为它们一定劣，或者它们不影响可行性。即它们的效果都被其他状态涵盖了。
例题：ABC443E
千万不要因为需要精确的差就放弃离散化。因为可以求作差之后的目标值的索引。
离散化处理的是偏序关系，自然也包括类似 $a_i \leq x+d$ 这种东西。这时可以考虑求出 $x+d$ 的索引（排名）。
例题：ABC444E
这个东西如果用动态开点权值线段树写会非常麻烦，线段树部分的空间还多个 log。当然由于 st 表本身也有一个 log，所以空间复杂度没有退化。我想应当是能够通过的。
最大独立集等于最小点覆盖的补集。
对于二分图，我们可以使用总点数减去最大匹配求出最大独立集的大小。但是具体的构造会更加麻烦。
例题：ABC445G
最大独立集的方案构造还是要先求最小点覆盖，然后取补集。
最小点覆盖的构造：从所有未匹配的左部点出发遍历，将所有可达的点进行标记。然后左侧所有未标记的点和右侧所有被标记的点构成的集合就是一个最小点覆盖。
证明需要用到最大匹配没有增广路的性质。
更加具体的：首先最大匹配中每条边需要一个点来覆盖，而各组匹配间没有交集，所以最大匹配边数是最小点覆盖的一个下界。
我们刚刚的构造中，每组匹配要么全部被标记，要么全部没标记，刚好取了其中一个点。
而对于非匹配点，左侧的全部没有被取，右侧的则不能通过左侧非匹配点抵达（否则就存在增广路），也完全没被取。所以我们的构造达到了点数下界。
对于每条匹配边，由于恰好取了其中一个点，都被覆盖。对于剩余的非匹配边，注意到右侧点一定是匹配的，否则就存在增广路，又矛盾了。所以一定是左侧点非匹配，这样，它出发遍历到的所有点，包括该边的右侧点，一定都被标记。
那么该边的右侧点被标记，即被选取，该边被覆盖。
于是证明了我们的构造是一个点覆盖。综上，这个构造是一个最小点覆盖，取其补集即为最大独立集。
对于需要去重的题目，我们常常考虑把一类元素的贡献拆到被查询的区间中该类元素的第一个上。
另外，在一些离线之后使用线段树和扫描线求解的题目中，我们也常常考虑“在下标 r 左侧的这类元素中的最后一个”，比如“如果这类元素在下标 r 前（包括 r）出现的最后位置比 l 更小，则它不对 [l, r] 区间产生贡献”。
一个排列的区间 MEX 等于其补区间的区间 min。
决策的变量一定要正确！
这个问题在期望 dp 中尤为关键。静态决策时决策的东西是“整个过程中的计划”。如果每个节点都能修改决策，决策的东西则是“当前在某个状态，我们进行某种转移使得未来代价最小”。
前者常常顺推，后者常常逆推。
一个例题：
如果设 (i, j, 0/1) 是第 i 节课上完，已经用了 j 次申请，第 i 节课是否成功换课在未来产生的最小期望就错了，因为这样我们可以根据当前的实际状态选择未来的最优决策。
正确的做法是对正确的变量决策：状态类似于 (i, j, 0/1) 代表前 i 阶段的计划中共有 j 次换课申请，最后一次是否申请的最小期望
转移时需要判断（通过枚举）上一阶段可能在哪里，以及现在可能在哪里。
2026.4.2
Abstract Painting
从前有一位画家，擅长在画布上画圆。作为一位有品味的画家，他发现如果按照以下限制画圆，得到的画布将看起来像一幅抽象画。
- 任何圆的圆心必须是 $x$ 轴上的一个整点。
- 任何圆上的点的 $x$ 坐标必须在 $[0, n]$ 的范围内。
- 任何圆的半径必须是一个不超过 $5$ 的正整数。
- 任何两个圆最多有 $1$ 个交点。
特别地，一个空画布也被认为是一幅抽象画，因为它不违反上述任何限制。
画布上已经画了 $k$ 个圆，没有违反上述限制。画家可以进一步在画布上画一个或多个圆以得到一幅抽象画，或者他可以什么都不画并声称这已经是一幅很棒的抽象画。他想知道他可能得到多少幅不同的抽象画。由于数量可能非常大，你只需要输出结果对 $10^9 + 7$ 取模的值。
输入格式
第一行包含两个整数 $n, k$ ($2 \le n \le 10^3, 0 \le k \le 5n$)。
接下来 $k$ 行，每行两个整数 $c, r$ ($1 \le c < n, 1 \le r \le \lfloor \frac{n}{2} \rfloor$)，表示有一个在 $(c, 0)$ 为中心，半径为 $r$ 的圆。
保证现在画的 $k$ 个圆是合法的。
输出格式
输出所有不同的方案，对 $10^9 + 7$ 取模的结果。
样例输入
| |
样例输出
| |
首先圆相当于区间，限制条件相当于区间不能交叉（要么不相交，要么完全包含）。
容易注意到一些 dp，大概就是类似前 i 个点的方案数。
转移好想：dp[i] = sum(dp[j] * f(j, i))，意思是放一个右端点为 i 的圆，其左端点为 j。f(j, i) 是 [j, i] 的方案总数。
注意，如果要计算前 i 个点的总数而不仅仅是有一个圆的右端点是 i 的方案数，需要有继承环节。
f 的计算和 dp 的计算类似，递归进去即可，记忆化，复杂度不会爆炸。
一个困难是初始的圆的限制。初始的圆必须出现在方案中，且会排斥一些其他的圆。
继承意味着当前点不画圆。如果当前点是某个初始圆的右端点，不能不画圆，也就不能继承。
j 是当前点上最大圆的左端点。这样来保证正确计数。
如果当前点上有些初始圆，j 不能比其中最大的小。
对于 f 的递归计算，类似的。
并且只要满足这个性质即可。
在 f 的递归计算中，我们考虑的不再是当前点上的所有圆，而仅仅是在当前区间 [l, r] 中的那些。
注意有些区间不能放圆，这时当前区间的总方案数就是 0.
一开始看错题了，误以为不是每种颜色对应一个区间。
然后想到了一些做法：枚举每种颜色，它的不同点能贡献 $k-1$ 个区间，逐个选取。
这样，一种颜色最多使得每个点被覆盖一次，总覆盖次数就不超过 $\lceil \frac{n}{k-1} \rceil$。
然而端点会被覆盖两次，这个做法就假了。同时，每种颜色只有恰好一个区间。
正解的思路是类似的。首先我们肯定只使用相邻两个同色点。
如果我们能把所有区间分成不超过 $m=\lceil \frac{n}{k-1} \rceil$ 组，每组内不相交且所有组的大小加起来不少于 $n$，那么我们就成功了。
那么我们从左到右枚举以使得所有区间自动按右端点升序排序。对于每个区间，如果它对应的颜色还没被使用过，我们试图把它加入到一个组里面去。当然，这个区间不能和组内的任何东西有交。
能加入就加入，否则直接放弃。
这一定能构造出 $n$ 个区间。
因为，当一个新区间被加入时，它限制住的区域里对每种颜色最多只有一个点（否则那个颜色就先被加入了）。
也就是说，新加入一个区间最多使得 $n$ 个区间无法放入这一组（加上这个区间自己）。我们用 $n$ 个区间就能挑出一个。
共有 $n(k-1)$ 个区间，为这一组至少能挑出 $k-1$ 个，一共能挑出 $m(k-1) \geq n$ 个区间，成功了。
容易预处理下一站和下两站。然后倍增。
没什么好说的，难度虚高。
贪心题。在某站使用加速之后，后面的抵达时间和出发时间都会变早，直到一个瓶颈（旅客抵达时间过晚）为止。
那么按瓶颈分段，每次在收益最大的段的开头加速。
注意不要试图动态维护瓶颈，每次暴力扫描即可，否则会极其难写。
猪很少。状压 dp。
考虑预处理哪些猪的集合可以被一发入魂。
注意到如果一个猪的集合包含另一个，取其中猪较多的那个。这样注意到两个集合间的交集大小至多为 1.
转移需要枚举所有一发入魂的集合，看似是 $3^n$ 的子集枚举，但实际上有效转移只有 $O(n^2)$ 量级。复杂度不高。
2026.4.3
用时：1h
前 i 个村庄建造了 j 个基站的最小代价？但可能有些村子没被覆盖
注意到每个村子可以接收到一个区间范围内的信号。
不妨钦定第 i 个村子一定修建了一个基站。
那么每次转移时，我们需要枚举前驱：对于 dp[i][j]，我们找到 dp[i’][j - 1]。
从这个候选项转移而来的代价是 c[i] + dp[i’][j - 1] + 中间没有被覆盖的村庄的总补偿金。
有了 $O(n^2k)$ 的做法。考虑使用线段树优化。
如果一个村子没有被前面的东西覆盖住，又不可能被后面的东西覆盖住，那么它必定需要补偿。
对于一个村子，当它不能被 i 覆盖时，我们对它的补偿金额进行前缀加，加到那些最后一个基站不能覆盖这个村子的候选项中。
最后取全局 min 加上 c[i] 即可。
调试时间较长。一个 bug 是重复 build 时没有清空之前的 tag。
用时：1h
ICPC CERC 2014 L, Outer space invaders
外星人入侵了地球。保卫自己，否则你会被消灭！或者被同化。或者被吃掉。目前还不确定。
有 $n$ 个外星攻击者，第 $i$ 个攻击者在时间 $a_i$ 出现，距离你 $d_i$，他必须在时间 $b_i$ 之前（包括 $a_i$ 和 $b_i$ 时刻）被消灭。
你的武器是一种区域爆破器，你可以给它设置任何给定的功率。如果以功率 $R$ 发射，它会瞬间摧毁所有距离为 $R$ 或更小的外星人。同时，它也会消耗 $R$ 个燃料电池。你可以在任意时刻发射武器，并且发射多次。
问摧毁所有外星人的最低成本，即多次发射的燃料电池消耗量之和。
输入格式
第一行包含一个整数 $T$，表示测试数据组数。
对于每组测试数据，第一行一个整数 $n (1 \le n \le 300)$。接下来 $n$ 行，每行包含三个整数 $a_i, b_i, d_i (1 \le a_i < b_i \le 10000, 1 \le d_i \le 10000)$，表示每个外星攻击者的信息。
注：原题面里没有写 $T$ 的范围，可以大概认为如果数据中都 $n=300$，那么 $T \le 10$。
输出格式
对于每组测试数据，输出答案。
样例输入
| |
样例输出
| |
做的迷迷糊糊，完全没有想到任何做法。
大概想到的东西包括按照距离从远到近考虑每个外星人，或者 DP 之类的。也想到了区间 DP 和离散化，但始终没有形成一个清晰的方向。
做法大概就是先离散化，然后区间 DP：设 dp[l][r] 是消灭所有出现和消失时间都在 $[l, r]$ 区间内的外星人所需的最小代价。
转移时，找到区间中距离最远的外星人，挑选一个良辰吉日干掉它。之后，如果另一个外星人在这个时间也出现过，那么它也会被干掉。所以我们接下来只需要处理掉那些消失的太早或者出现的太晚的外星人。
形式化的：dp[l][r] = min(dp[l][r], dp[l][mid - 1] + d[max_i] + dp[mid + 1][r]
这个题的启发大概就在于，如何处理外星人的位置是一个区间的情况。同时又是一个考虑最大元的技巧来解决击杀一个外星人之后不知道剩下了哪些外星人的问题。
二分。
我们可以找到所有长于目标值的路径。然后我们需要砍掉一条边，这条边应当出现在所有过长的路径中，且足以让最长的路径符合要求。所以可以得知这条边长度的范围（不小于某个值）。
不妨树剖，统计每条边被覆盖的次数。然后暴力扫描每条边，如果覆盖次数等于目标路径总数，则观察它是否合法。如果存在一条合法的边，那么当前值就是可满足的。
注意到虽然每次检查复杂度很高，但检查次数在对数级别，于是总复杂度可接受。
当然可以不用树剖，树上拆分复杂度少一些 log。
犯了一个错误：树上差分之后子树和直接就是当前点向父节点的连边被经过的次数，不用再减去父节点的子树和。
2026.4.7
用时：1.5h
首先不难想到一些 DP：dp[i][j] 是当前在第 i 天，上一次休息在第 i - j 天（即当前已经连续跑了 j 天）的状态对应的最大能量值。
很好转移，复杂度 $O(nk)$，无法通过。
这个题的最大数据范围中 n 达到了 $10^9$ 级别。这提示我们离散化。
为了离散化，我们需要一个简单的观察：
一段连续跑步的时期必定从一次挑战的约束区间的左端点（$l_i$）开始，并在某个约束区间的右端点（$r_i$）结束。
很好理解。因为如果我们从没有任何挑战的时候开始连续跑步，不如不跑步，这不会损失任何东西。同样的，如果我们在挑战都结束之后继续跑，也无法获得任何东西。这是一个贪心的性质。
自然，由此我们可以离散化。离散化哪些点也需要注意，这坑了我很久。我们等会再详细展开。
离散化之后，复杂度仍然在 $O(m^2)$ 左右，非常高。我们的 DP 有平方量级的状态，非常不好。太多的状态使得无法优化复杂度。
精简一下状态。一个经典的技巧是，每次转移一次性考虑最后的连续段（即连续跑步的时期），而不是一个一个的往最后的连续段中添加元素。
应用这一技巧。设 dp[i] 是在第 i 天，当天休息获得的最大收益。
转移时自然是枚举最后一个连续段。具体的：
$$ \mathrm{dp}_i = \max_{j = \max(i - k - 1, 0)}^{i - 1}(\mathrm{dp}_j - d(i - j - 1) + \mathrm{reward}) $$其中 $\mathrm{reward}$ 代表连续跑这一段能完成的挑战的总收益。
注意到这个转移具备非常好的性质，以至于我们可以使用线段树优化 DP。
为什么？
我们的转移中，i 不断增加，相当于一个扫描线。这时，i 每右移一段，前面的所有可能转移决策都会减去同样的一堆 d，这是一个前缀加法问题。
同时，$\mathrm{reward}$ 也非常有趣。当我们的 i 抵达一个挑战终结之后，只要转移的决策 j 足够早（早于挑战开始的时刻），这个挑战的奖励就能被获得。所以这也是一个前缀加法。
最后我们需要查询一个区间最大值，就做完了。
不过这个题让我调了非常非常久。有一些坑点：
离散化的选择
我们应当选择那些可能作为一个连续段开始/结束的点，即 $l_i-1$ 和 $r_i+1$，而不是 $l_i$ 和 $r_i$。原因很简单，因为我们的状态设计中钦定当前这天休息，枚举的连续段是开区间。继承关系
我们可能很久不跑步，直接继承之前的某个状态。
在没有离散化时，这不需要额外的处理，因为j等于i-1的转移自然包含了这种情况。但离散化之后，很多时候前一个点和后一个点之间的距离非常大，这会导致我们的 DP 只考虑一直跑步的情况，而不考虑停下来休息直接继承的情况，需要特殊处理。精确控制减去多少个
d
从上一个点i移动到下一个点j时，对于所有更早的转移决策k，它们都会因为多跑了j - i天而需要减去这么多个d。但i本身不一样，它只需要减去j - i - 1个d。所以我们需要对它额外加入一个d，这可以在将新的点的dp值加入线段树时顺便完成（给线段树中不加入dp[i]而加入dp[i] + d）以减小常数。
2026.4.9
用时：0.5h
没能独立想出来。主要原因是没有把路径拆成两半。
直接考虑一个拐弯的、前一半上升后一半下降的路径是困难的，把它拆成上升段和下降段就好得多。对于上升段和下降段分别推式子，做一个类似参变量分离的操作，就发现等价于每个观察员统计子树内某个量等于观察员自身某个属性的点的数目。
这个相对是好做的。我们可以用一个全局桶和一种类似树上差分的技巧。每个点的桶等于子树里所有桶的和。
直接暴力做复杂度会退化掉。所以在进入子树时不清空桶，仅仅记录进入子树前的桶在这个点关心的位置上的值。统计答案时用桶当前的计数减去进入子树前的值。这可以看做是只清空了一个点。
另一个需要注意的点是不要让一个人的路径的 LCA 把这个人算重。
2026.4.10
用时：1h
一种菜使用超过一半是一个很有趣的条件。因为不可能有两种不同的菜同时使用了超过一半。
所以就考虑容斥。
全集，是所有行的和加一的乘积减去一。因为每一行可能选择一种食材或什么都不选，食材的总选择就是不同种食材的和（加法原理）。减一是因为不能做一桌空集。
不合法的方案中，我们考虑枚举哪种食材用了超过一半次数。然后我们用一个类似组合数的 DP 来处理它：dp[i][j] 代表前 i 行，选择的该种食材数目比其他食材多 j 的方案数。
转移挺好想。之所以这么写而不用“前 i 行选 j 个该种食材的方案数”是因为我们可以忽略某一行，因此选择的食材总数不确定，可能会被迫加一维而超时。我们采用的这种 DP 方案中，一些方案不合法的充要条件是选择一种食材的数目超越了其他食材被选择的总和，而无关食材总数是多少。
用时：无穷大
被证明击杀了，不会证明贪心构造最优，做了一上午
知道结论之后就有一个 DP：设 dp[i] 是长度为 i 的前缀的最优划分的最后一个划分点（即最后一段是 $(\mathrm{dp}_i, i]$），s[i] 是前 i 个元素的总和（前缀和）。
那么对于一个 i 和一个 j，j 可以作为 i 的最后划分点，当且仅当 j 的贪心构造（同时也是最优构造）的最后一段和小于 s[i] - s[j]。原因相对显然，因为如果 j 的贪心构造不能作为 i 的前驱状态，那么 j 的非贪心构造的最后一段和更大，就更加不行了。
这样，我们需要在所有 s[j] - s[dp[j]] <= s[i] - s[j] 的 j 中取最大值。参变量分离（又是这个经典技巧）：2 * s[j] - s[dp[j]] <= s[i]。
显然这可以单调栈 + 二分。因为一个更加靠左的 j 如果它的特征值 2 * s[j] - s[dp[j]] 还更大，就绝对用不上了。我们就可以维护单调递增栈，二分最后一个特征值不超过 s[i] 的 j。
注意到 s[i] 递增，所以可以进化为双指针去掉一个 log。这个双指针可以使用类似单调队列的方法实现。
用时：2h
一看数据范围如此小，非常搜索。稍微算一下，爆搜能过。
代码写的比较神秘，一个离奇的错误导致输出 -1：把 new_state 声明为 decltype(cur_a) 类型导致它变成了引用，后续对它的更改莫名其妙改到了 cur_a 上。
然后注意即使一次交换没有任何用（交换的两个方块是同色的）也不能忽略它，因为我们要求使用恰好 n 步完成游戏。
另一个错误就是注意如果一行有 7 个数，数组不要越界；同时也注意读进行尾的 0，否则之后的读入就会读到错误的值。
2026.4.14
用时：1h
注意到这个题的本质是偏序集排序/DAG 拓扑排序。要点是边数不会太多，每个 s 串只能贡献最多 16 条模式串间的边。所以直接做就行了。
具体的：如果 s[i] 对应的模式串能够匹配 s[j] 对应的串，我们连边 $j \to i$ 代表 s[j] 对应的串必须在 s[i] 对应的串前面。然后拓扑排序，如果遇到环则无解。
这个连边需要高效完成。我们枚举每个 s[i]，枚举 16 种可以匹配 s[i] 的模式串，找出其中“出现”（即作为其他 s[j] 对应的模式串）的那些，并将这些模式串与 s[i] 对应的模式串连边（注意去掉自环）。“找出出现”一步可以考虑简单的 map 标记或者 hash table 之类，不算困难。
[USACO21JAN] Uddered but not Herd G
用时：1.5h
题意相当于将字符串 copy 很多遍然后取其中一个子序列。
假设我们已经知道了字母表的相对顺序，那么这很简单了：模拟一下，顺序扫描每个字符，如果当前字符不在之前字符的字母表顺序之后，那么答案加一。
那个很长的字符串自然简化为很少（不超过 $26^2 = 676$）对邻接关系（每种字母紧接在在另一种字母后出现了多少次）。
枚举相对顺序是没救的，这最好情况下也是 $n! \times |\Sigma|^2$，只能过前五个点。
$\sum_{i = 1}^n \sum_{j = 1}^{i - 1} \mathrm{cnt}[p[i]][p[j]]$
感觉非常状压，但是怎么弄呢？
我 是 唐 人
没有推式子导致的。上面这个东西显然可以转化为每次向排列 $p$ 的末尾添加一个元素。我们只需要记录哪些东西已经使用过即可，直接做状压 DP 就是对的。
2026.4.15
用时：2.5h
一种简单的想法：dis[u][k] 代表在 u 这个点，已经用过 k 次翻转的最短路。
但一个问题是，k 最大可能达到 $O(n)$。这个做法是平方或者平方 log 的，非常劣。
让我们来发掘题目性质。题目看上去是一般的有向图，但数值很特殊：边不带权；每次操作的代价都是 2 的幂。
注意到不管 k 是多少，只要奇偶性相同，那么连通性就丝毫不变。
所以状态可以变为 dis[u][0/1] 代表抵达 u，且用了偶数/奇数次反转的最短路以及具体的反转次数。
这里，我们是应该优先最小化最短路还是反转次数呢？
其实我们记录的最短路可以是不包含反转的代价的路径长度。这样，发现无论如何，我们的反转次数最多只有 $O(\log n)$ 种不同的情况。
这个断言有依据吗？不知道。
考虑一个宽松的上界：$2 \log n$。这样，我们相当于断言了最短路长度不超过 $n^2$。考虑最初我们的 dp 状态只有不超过 $n^2$ 个，看上去很有道理。
那么我们只需要跑 dijkstra 就可以了。有一个技术难点：如何比较两个状态？
$(\mathrm{len}, k)$ 代表已经使用了 k 次反转，路径长度为 len。那么实际路径长度就是 $2^k + \mathrm{len} - 1$.
在 k 较小（不超过 63）时，直接比较。当 k 很大时，直接比较 k。
钦定顺序/错解不优/正则化/dijkstra 动态维护数值依赖的顺序/dijkstra 图的二叉化/状态削减
DP 的一些常用方法。可以熟记常用。
一个例题：[NOIP 2017 提高组] 宝藏
钦定按层转移以降低状态数。假设每层新加入的点都能连接到相对于之前集合的最短边上。虽然可能这是错的（最短边并不在叶子上），但错解不优，总有一个相应的合法方案比错误方案更优。
2026.4.17
用时：1h
写出了若干个 bug。最隐蔽的一个是二分写挂了：使用了 while (l < r) 而在二分结束之后试图使用 l <= r 判断 l 是否合法，完全忽略了 l 与 r 初值相等的情况。其实如果某一步二分中 r - l 等于 2，也可能造成最后对一个长度为 1 的区间完全不判断就退出……总之最后多 check 一次合法性为好。
题目的做法就是二分，之后需要贪心检验合法性。如果想到 DP 方向就做不出来了。
大概就是从子树下面蔓延上来一些链，但从一个点到它父亲的边只能通过一条链。我们优先在当前点制造尽可能多的匹配，然后挑一条最长的不会降低匹配数的链传递到父亲。
用时：1h
观察到可以把整个方阵划分成每行的前面部分（长度为 $m-1$，即每一行除去最后一个人之外剩下的部分构成一个序列）和最后一列。每次操作都是区间平移。
这个东西可以动态开点线段树+线段树上二分或者直接平衡树解决。线段树要好写的多，只是空间可能多一个 log。这道题不卡空间，不过如果想要优化，孤链压缩可以解决。
拉格朗日插值优化 DP。自己独立做的进度等于 0.
关键观察：总步数可以转化计算：第 $t$ 步时，还有多少个点在场内。
总步数 = $\sum_{t=0}^{\infty} (\text{第 } t \text{ 步后还在场内的起点个数})$。
对于某一维 $i$，在第 $t$ 步时，如果这一维相对于起点的最大正向位移为 $mx_{i,t}$，最大负向位移为 $mn_{i,t}$，那么只有满足 $1 - mn_{i,t} \le a_i \le w_i - mx_{i,t}$ 的起点才在这一维内。
这一维可用的长度为 $W_{i,t} = \max(0, w_i - (mx_{i,t} - mn_{i,t}))$。
第 $t$ 步后场内点的总数为 $\prod_{i=1}^k W_{i,t}$。
总之我可能是被这个题吓住了。按理说是应该想到这个转化的。
调了无穷久。一些错误是，我插值和后续计算边界时忽略了我使用的 m 是在前 k+2 轮模拟之后还要继续多少轮，是增量而不是总量。
另一个错误是，最后一个不完整的周期的模拟：注意判断正确的可行区间。具体就是应该考虑每个点的历史最值。以及中间被跳过的 m 步对历史最值的影响也需要被正确计量。
2026.4.20
用时：1h
DSU on tree 模板。然而第一次写这个东西，就写挂了一个地方：
第二次统计轻子树贡献时不应使用计算答案的 dfs 函数，而应该使用仅仅累加的 add 函数。
使用 dfs 会导致 max_v 和 max_c 以及 cnt 中的一些位置被意外清零。同时，这会引起复杂度退化（因为子树内各个点的轻子树被多次遍历）。
2026.4.22
[USACO21DEC] Closest Cow Wins S
用时：1h
考虑在敌方两个相邻的牛之间放一些牛。假如放了 2 头或更多牛，则能占据整个区间，否则可以占据区间长度的一半，且是任意的一半长度。
不难想到对于所有区间，我们计算出放 2 头牛或放 1 头牛的收益（对于两端的开放部分，一头牛即可全部占据）。变成一个类似分组背包的东西，但复杂度太高。我们注意到可以直接枚举多少个区间放 2 头牛，多少个区间放 1 头牛，然后贪心选择即可。
直接贪心选择仍然不那么对。但是注意到，我们可以把 2 头牛的可能性拆分成 1 头牛和增量，变成独立的 01 背包，然后跑贪心。这一定是正确的，因为唯一非法的可能性是不选第一头牛而直接选第二头牛，但这是不优的。因为两头牛管辖的区间长度是一样的，而第一头牛一定放在这个同等长度区间的收益最大的地方。
可能会怀疑这样一种情况：我们只能选连续的一段区间，所以选的区间里面的美味度和就不能比剩下一半由两个区间拼起来的东西大。但这是不存在的，我们至少有一种方法可以用一个区间取到整个区间中不少于一半的美味度：考虑长度为一半的前缀和长度为一半的后缀，其中必然有一个满足条件。
用时：1h
总之就是用一个数据结构（比如 BIT 之类）从左到右扫描一遍。每加入一个元素都更新当前答案。
更新答案分两部分：一部分是以前加入的比当前元素小的元素，对它们求和。另一部分是以前的比当前元素更大的元素。对这部分，我们暴力枚举当前元素的若干倍，在这个区间之内我们求已有元素减去当前元素的若干倍的和。
注意，其实不仅仅是当前加入的新元素作为模数去模之前的元素，另一部分贡献是以前的元素作为模数模当前的元素。但这部分贡献是比较类似的。
由于值域有限，元素互异，调和级数保障了复杂度的正确性。
用时：1.5h
怎么想也没想出来。最后官方题解的做法是比较有意思的：考虑“每个被保留的点确定了哪些边界”。
这个东西直接暴力枚举通过一些优化也能做。不过状压 DP 写起来更简单：考虑前 i 个点，从中保留一些，确定的边界集合是 s 时的最大收益。
下边界和左边界被确定时会产生 $-2x_i$ 或 $-2y_i$ 的贡献。上边界和左边界则是 $2x_i$ 或 $2y_i$（这是一个类似于分离变量的方法得到的）。再加上不被保留的点产生 c[i] 收益，就能转移了。
没能独立完全做出来。不应该。
想到了可以用两次询问比较出两个数的大小关系，但没能注意到同时还能确定一个数的数值。
并且完全陷进了“先寻找 $n$，然后依次确定其他位置”的思维定式中，寄寄寄
2026.5.7
把周作业里面比较值得说的都写一下。
后三个题不会。前七个题独立解决了。
结论比较惊人。一贯的 AT 风格。
启发是，要有“将可以自由调整的部分删去，比较剩下部分”的意识。上次 ABC D 题也遇到类似的东西。
还涉及到一个有趣的引理：如果对任何两个范围重叠的操作，操作顺序无关紧要（会得到相同的串），那么整个串的操作顺序也无关紧要。
这里的意思是，对两个操作 A 与 B，先操作 A 和先操作 B 在这一步之后得到的串一模一样。
还有就是思考如何自由移动 ABC 这个子串。
想明白这些东西之后大概就能做出来了。
大失败。只会使用 $O(n^2 V)$ 暴力 dp，连 $O(nV)$ 都没想出来。
这是不应该的。事实上，这个题直接套用 LIS 的做法就能设计出 $O(nV)$ 的 dp：dp[i] 代表异或和为 i 的上升子序列中末尾元素最小的值。
做到这里就算是做进去了。不过本题没有 LIS 那样好的单调性，不能简单的套用二分，只能 $O(nV)$ 暴力枚举。而这会超时。
很自然的可以想到维护哪些东西可以是转移的前驱，r[i] 代表所有 dp[j] 小于 i 的 j 构成的集合。
这个东西直接暴力维护：我们每遇到一个点，就遍历对应的 r[a[i]]，检查其中所有值可能的转移，并更新 r，向由于 dp[x ^ a[i]] 变小新产生的比它大的 j 对应的 r[j] 中添入 x ^ a[i]。最后清空 r[a[i]]。
每个 x 在每个 r[i] 中只会被加入一次并处理一次。所以总复杂度变成了 $O(n + V^2)$。
MEX 集合的 MEX 就是找哪个数不是任何子段的 MEX，并最小化这个数。
那么我们考虑什么情况下，一个子段的 MEX 会是一个 $k$。
显然，这个子段不能包含 $k$，而且必须包含所有 $[1, k)$ 中的数。
这样，我们想到把整个数组按照 $k$ 划分成若干个不含 $k$ 的极长连续子段。不难发现，这些子段本身是最有可能满足 MEX $=k$ 的。
于是我们就使用扫描线去处理。从左到右扫描，扫到下标 $i$ 时，我们就处理 $(\mathrm{pre}_i, i)$ 这段区间（假如它非空）。我们检验其中是否含有所有 $[1, i)$ 中的数。这容易使用线段树处理和维护。
会漏去很多后缀的 MEX。所以特殊处理一下后缀即可。
看上去非常麻烦。不过注意到，拆点之后每个点度数恰为 2。意味着整张图是一堆环。而我们要通过重排“一行”（来自同一个原始点的点）点之间的边连接，将环合并成一个。
这就容易了。注意到交换一行能够将其中所有环合并，而一行上的环最多不超过两个。于是将一行建模为一条边，直接最小生成树即可。
眼神要好，经过分析，不难发现每条边需要一个第二类点。于是这显然是二分图（还需要跑一个背包/子集和），随便做一做即可。
感觉反而比 DE 难。
注意到我们每次操作消耗至少一个连续段。于是考虑利用“冗余”的长度，即长度超过 1 的连续段。
考虑贪心。不难想到优先使用靠前的冗余。没有证明但非常正确。
2026.5.8
有趣的题。要点是看到值域很小，于是将每个变量的每个可能取值都建模为一个变量：$p_{i, j}$ 意味着第 $i$ 个变量是否不超过 $j$。
然后就好做了，使用 2SAT。
要点是注意到未知数太多而约束太少，于是可以先随便递推出一个解，然后发现它可能会违背值域约束。于是我们考虑使用一些偏移量进行调整。
偏移量需要满足一些条件。具体的，每个 $2\times 2$ 矩形中偏移量的和必须为 0。
这个条件让我们想到 $(-1)^{i+j}$ 这个因子。因为如果我们令 $\mathrm{delta}_{i, j} := (-1)^{i + j}c$，刚好满足所有约束。
当然这么做显然不够。直觉的，我们大概需要给每行每列一个自由度，于是令 $\mathrm{delta}_{i, j} := (-1)^{i + j}(r_i+c_j)$。
可以证明，这样我们能够表达出所有可能的解。于是使用差分约束添加值域约束并求解即可。
具体的证明，我们将所有约束看做线性方程组。可以计算方程组的秩（注意到它的矩阵是行满秩的），于是发现我们提供的变量数是够的，而且多出一个。注意到我们的变量中多的一个对应差分约束系统的整体平移。剩下的东西可以证明是线性无关的。