标了 * 的是我自己胡出的 Ad-hoc 东西。

图论

树

• 两个点集 \(S\cap T=\emptyset\) 分别有直径 \(d_S=(u_S,v_S),d_T=(u_T,v_T)\)，那么必然有 \(d_{S\cup T}=(u,v),u,v\in \{u_S,v_S,u_T,v_T\}\)。题。

图

优化建图

• 固定长度分块。*题。
• 前缀和。*题。
• 倍增。*题。

计数

容斥

• 学会自己配容斥系数。题。
• 无向图定向计数。典，典，题。
• 反射容斥。典。
• 子集反演。题。

3

• \(1,2,3\) 异或得另一个。题。
• \(1,2,3\)，\((-x-y)\bmod 3\) 得另一个。
• 三进制 FWT。题。

生成函数

• 泰勒展开。题。
• 集合幂级数。题，题。
• 拆贡献。典。
• 手推一些组合数恒等式。

计数·杂项

• Matrix-Tree 定理结合特殊矩阵行列式。题。
• 分拆数很小。题。
• 线头 dp。典，题。

数论

• 积性函数卷积。题。

数据结构

\(\log^kn\)

• 单调栈大小结论（笛卡尔树启发式合并）：如果 \(l_i\) 是 最大满足 \(j<i,a_j\le a_i\) 的 \(j\)，\(r_i\) 是最小满足 \(j>i,a_j>a_i\) 的 \(j\)，那么有 \(\sum\limits_{i=1}^n\min\{i-l_i,r_i-i\}=O(n\log n)\)。题，题。
• 线段树合并优化 dp。题，题，*不是二叉树的 Minimax。
• 可持久化离线转在线（如数点、线段树合并），题。
• 双指针。题。题。
• 二分。题。
• 线段树合并与分裂结合。P2824 加强版。
• 颜色段均摊。题。
• k-merging。题。

\(\sqrt n\)

• 数论相关可以根号分治。题。
• 弹飞绵羊。本尊，题。

网络流

• 上下界网络流。题。
• 网格图转二分图。题。
• 用最小割建模。典，题。
• 二分图最大独立集。任意固定步长的马互相攻击连边都构成二分图。
• 疫情控制。本尊，题。

真·杂项

• 根号分治，然后把根号放到指数上面。题，题。
• 交互题最优解 dp。题。
• 插值。典，题。\(O(n^3)\) 二元多项式卷积。
• 连续转离散。*2log 过不去，题。
• 奇怪随机化。*题。
• 格雷码。*题。
• 斜率。题号找不到。