算法 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 优化求交集即可。