套路积累

_kpsum · 2024-10-15 16:29:10 · 个人记录

• 树上单点改，路径查的问题，如果询问有可加减性，就可以放在括号序上，左括号值为正，右括号值为负。询问 (u,v) 等价于括号序上 [p_{lca(u,v)}, p_u]+(p_{lca(u, v)}, p_v]，p 表示一个点左括号的位置。（明日之星）

• 对于给定操作序列，每次询问只执行时间在 [l,r] 之间的操作，可以离线询问，然后扫描线扫 r，将一个操作产生的贡献打在这个贡献依赖的最早操作上，询问 [l,r] 即求贡献数组上 [l,r] 的和。P11191，P5524。

• 染色使得……相等或绝对值之差 \leq 1 等问题可以考虑欧拉回路，如果对点染色，则可能需要转为对边染。P8326，CF547D

• 统计满足与区间有关条件的括号序列个数，可以考虑画出前缀和折线图后，从上往下一层层插入。ARC117E

  • 本质上是连续段 dp，用于处理状态转移依赖邻项的计数问题。（考虑插入一个元素有扩大、独立、合并三种选择）P7967

• 不合法必不优：对类似 \max_i\{ A_i - \min_j\{B_j\} \} 的式子求值时，可以直接去掉 \min，变为 \max_{i,j} \{A_i-B_j\}，因为若 B_j 不取最小值，则必定不优。CF1149C

• 笛卡尔树经典套路：

  • 隐式 O(n) 建树：单调栈处理出左右第一个比 i 大的位置 L_i, R_i，则节点 [L_i,R_i] 的最大值是 i。
  • 笛卡尔树上启发式合并：每次只枚举最大值左右两侧中大小较小的区间。P4755
  • 笛卡尔树 O(n) 求所有长为 i 的区间最大值的最小值（所有 i）。
  • 有一类题是先建笛卡尔树，然后斗一个二维的 dp，再用线段树合并斗优化。（笛卡尔树也可以换成其他二叉分治结构）P7219，ABC275H

• 莫队块长取值：莫队时间复杂度为 O(\dfrac{n^2}{B} + qB)，均值一下得到 B=\dfrac{n}{\sqrt{q}} 时最优，时间复杂度 O(n\sqrt{q})。

• 静态 O(\log n) 求区间 \text{mex}：可持久化权值线段树记录这个数最后一次出现的位置，查询的时候在第 r 棵线段树上二分，找到最小的、最后一次出现位置在 l 左侧的数，这个数就是所求的答案。

• Shopping Plans' Tirck：解决一类求“所有状态中价值前 k 小/大 的状态”的题的高妙方法，其中 k=O(n)。blog

• 在树上，若设一个点的点权为其临边的边权异或和，则边权全为 0 等价于点权全为 0。APC001F

• 对于一类求“所有可能的状态的价值和”的计数题，考虑计数转期望。P7986，AGC028B

• 如果将区间 [l,r] 视作平面上的一个点，点的颜色是这个区间的 \text{mex}，那么这个平面由 O(n) 个矩形构成。

• 求 1 到 n 的最大异或和路径：建出生成树，对于一条非树边 (u,v,w)，将它构成的环的权值即 dep_u \oplus dep_v \oplus w 加入线性基。然后把 dep_n 放进线性基里跑个贪心即可。P4151

• 在树上，把所有叶子按 \text{dfs} 序排成一个环，相邻两点的距离之和就是树上所有边权的和的两倍。

  • 推广一下，当树上有若干个关键点时，把这些关键点按 \text{dfs} 序排成环，相邻两点的距离和是它们构成的虚树上的边权和的两倍。

• 对集合中元素出现次数有限制的题，考虑加和哈希。（11.16 联考 T3）

• 给出树以及函数 f，对于 l,r,x，询问 \sum_{l\le i \le r} f(\text{lca}(i,x))：设一个点的点权 a_i=f(i)-f(fa_i)，那么 f(\text{lca}(i,j)) 相当于将 i 到根的链上所有点的点权系数加一，再查询 j 到根的链上所有点的点权乘上系数的和。这样原问题就可以通过离线扫描线的技巧转化为链加，链查询，可以树剖做到 O(n \log^2 n)，也可以用全局平衡二叉树做到 O(n \log n)。P5305，P4211

• 折半警报器：blog

• 二维哈希：\big(\sum_{i,j}{p^i q^j a_{i,j}}\big) \bmod P。 P2601

• 一类操作是将序列的一个子集中的元素变为子集的中位数的题目的两种套路：

  • 先二分，然后转化成 01 序列。
  • 设一个合法子集的中位数是 x，则可以通过 \log n 次操作让整个序列都大于等于 x。

• 对于一个排列 p，区间 [l,r] 中的数构成连续段当且仅当 \max-\min-(r-l)=0

• 对于一颗树，编号在区间 [l,r] 中的点在树上构成连通块当且仅当 r-l-导出子图边数=0

• 树上阶梯博弈：每次取一个点上的部分石子移动到其父亲，SG 值到根距离为奇数的点的石子数异或和。CF1498F

• 单个物品重量小的背包问题的更优解法：

  • 以下记 n 为物品个数，w_i 为物品重量，v_i 为物品价值，c_i 为物品数量，m=\max w_i，W 为目标重量。
  • 完全背包（可行性，最优化，计数）：考虑数位 DP，二进制下从低位到高位考虑每个物品选择数量，在 DP 状态中记录当前重量和的进位以及当前重量和是否小于背包容量，时间复杂度 O(nm \log W)。CF1290F
  • 多重背包（可行性，最优化）：一开始先按性价比排序从大到小排序，贪心加入物品。设当前背包中的物品体积和为 S，显然 S \in [W-m, W]。考虑对贪心后的结果进行调整，并且一定有一种调整顺序使得任意时刻 S \in [W-m, W+m]。考虑如果调整过程中 S 重复到达一个重量会怎么样，因为一步调整一定是删除一个贪心中选中的物品，或者加入一个贪心中没选的物品，所以调整后背包的性价比会变劣，所以重复到达一个重量是不优的。那么在调整的过程中最多更改 2m 个物品，所以做一个容量为 O(m^2) 的多重背包即可。时间复杂度 O(nm^2 \log c) 或 O(nm^2)。P8392
  • 01 背包（可行性）：第一步与多重背包相同，根据贪心将物品分为左右两部分。设 f_{l,r,w} 表示之调整区间 [l,r] 内的物品能否凑出 w 的偏移量，直接做是 O(n^2m) 的。考虑优化，设 g_{r,w} 表示f_{l,r,w}=1 的最大的 l 是多少，转移暴力枚举左边删掉哪个物品。均摊一下得到时间复杂度 O(nm)。ABC221G

• 网络流：

  • 对于一些费用流中的特殊边权，如果边权为关于流量的函数且这个函数是下凸的，那么可以通过将这条边拆成非常多条流量为 1 费用依次为 f(1),f(2)-f(1),f(3)-f(2),\dots 的边解决。 P4249
  • 如果题目中的限制与元素大小有关，可以考虑最小割切糕模型。对于每个元素建出 V 个点，连 (i,i-1,10^9)，这样一种割中该元素一定是一段前缀归 S，后缀归 T。ABC397G，ARC142E
  • 平面图的存在一条路径等价于对偶图上两点不连通。

• 对一个序列上相邻两个位置操作的题目，考虑黑白染色。

• 对于一类操作是每次等概率选一个可以操作的点，然后把该点和其他一些点变为不可操作的点，问期望能操作的次数。可以转化成等概率随机一个排列，按顺序考虑每一个点，统计有效操作的点的个数的期望。ARC165E，ARC150D