算法 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。