Trick 3.0

AGC027E

• 操作的不变量

对于做若干次操作的题目，观察操作，找到操作中不会改变的量，将能通过操作得到的转态归纳。如此题中，当 \(a=1,b=2\) 时，修改操作就不会改变序列 \(mod\ \ 3\) 的值。

• 本质不同的计数

类似此题中的结果有多少种本质不同的情况，往往从初始去dp修改是困难的，由于本质不同的条件，只好去dp答案。常见的，用一种不重不漏的方式映射答案，这种映射为满足不漏的性质，通常使用贪心确定，例如在此题中，将一个合法的答案映射为原序列的一种划分，且满足前缀最短，在这样的性质下，某一位对应的区间一定是从当前出发的最近一个合法区间，这样就满足了每种合法答案的唯一性。

[Ynoi Easy Round 2021] TEST_68

进行多次最优性查询且查询集合有大量重复的时候，可以先找到全局最优，此时只需要对不包含全局最优的查询操作，查询集合可能会有性质。

构造倒水

• 分治构造

对于构造从始状态到终转态，步数有限制，可以找到多种构造方式，通过分治的方法使得无论何时都能满足条件。对于 \(n\) 中构造方式，每种方式为 \(a_i\) 次（关于某个变量的多项式），其非严格上界为 \(\frac{\sum a_i}{n}\) 。

[20251119] 换来换去

• 卷积式的前缀和

想要求出卷积式前 \(n\) 项往往至少要 \(O(nlogn)\) 才能做，但是卷积式前 \(n\) 项的前缀和可以枚举一项，另一项用前缀和优化做到 \(O(n)\) 。

此题的推导中还需要用到二项式定理，在实际运用中还是应该提高对二项式定理形式的辨识。

异或

• 可持久化线段树卡空间

初始节点 \(2n\) ，每次修改增加 \(O(logn)\) ，注意到每 \(\frac{n}{logn}\) 次修改重构一下就能满足空间为 \(O(n)\) 。

• 区间修改的可持久化

通常的区间修改需要实现 \(pushdown\) 操作，但这个东西可持久化会非常麻烦，所以能用标记永久化就用标记永久化。

度与好

• dp状态设计

dp的本质是决策当前步，然后转化成若干个子问题，状态的设计是通过增加限制的方式使得它能被分为子问题。例如在此题中，子树加的操作是不能够直接将其分为若干个子问题，因为在当前步做子树加会修改后面的状态，也就是有后效性。观察到每个点也只需要关心从祖先做的子树加操作的和，所以就将这个设进状态里。

• 区间修改的线段树合并

若是一个点没有有效儿子，那么不下放标记，此时说明这段区间的值相同，合并时可以直接贡献到另一个点的标记上。

[COCI 2021/2022 #5] Fliper

• 欧拉回路与边染色

边染黑白颜色，要求每个点的边两个颜色次数相同。跑欧拉回路，按步数的奇偶染色，正确性显然。