笔记

笛卡尔树 学习笔记

碰到好多次了,系统的整理一下。 定义 笛卡尔树跟 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 &...