算法 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 的迭代器。