长链剖分常用于优化一类特殊的动规，它可以在满足某些要求时，将 $\mathcal O(n)$ 的转移复杂度均摊为 $\mathcal O(1)$。此外，长链剖分还有一些优秀的性质，目前长链剖分在信息学竞赛中应用很广泛。 定义 ...

树上启发式合并 (dsu on tree) 可以在较优秀的复杂度内解决某些树上离线问题。 引入 考虑这样一个问题： 给一棵 $n$ 个点的有根树，求每棵子树的颜色种类数。 考虑暴力，当我们要求 $x$ 的子树的答案时...

碰到好多次了，系统的整理一下。 定义 笛卡尔树跟 Treap 的定义是一样的： 二叉树 每个节点有一个键值 $(k,w)$。 $k$ 满足二叉搜索树的性质。 $w$ 满足二叉堆的性质。 严格意义上讲，Treap 是 $w$ 随机...

Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。 前置知识 高斯消元 在 $\mathcal O(n^3)$ 的时间复杂度下解线性方程组。 【模板】P3389 【模板】高斯消元法 #define Fail r...

数论与图论的结合 基本思想 通过同余构造某些状态，状态之间的关系类似于两点之间的带权有向边。 那么可以以此建图，将某些问题转化为最短路问题，再使用具有优秀时间复杂度的算法求解。 【例题】P3403 ...

线段树的一个小应用 核心思想 考虑这样一个问题： 有一些操作，每个操作只在 $l \sim r$ 的时间段内有效。 有一些询问，每个询问某一个时间点所有操作的贡献。 对于这样的询问，我们可以离线后在时间轴...

一直莫名不想碰的一个专题 基础知识 点、向量模板 const ld eps = 1e-10L, PI = acos(-1); struct P { ld x, y; inline P() {} inline P(ld x, ld y) : x(x), y(y) {} inline P &ope...

OI 中的微积分——自适应辛普森法 引入 我们要计算这样一个式子： $$\int_l^r f(x) {\rm d}x$$ 我们显然不可能让计算机去推柿子。 那怎么办呢？ 二次函数的定积分 对于一个二次函数 $$f(x) = ax^2 + bx...

OI 中的群论 理论 置换群 置换就是把 $n$ 个元素做一个排列变换，一般地，把 $i$ 变成 $a_i$ 的置换记为 $ \left( \begin{matrix} 1 & 2 & \dots & n \\ a_1 & a_2 & \dots &...