这个笔记想写得稍微详细一点，部分内容来自我自己之前的博客: OI 里的数学内容整理（提高组）。 其中一些公式是 AI 从 PPT 上识别的，格式混乱，还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…

图匹配 二分图匹配 判定 静态：黑白染色。 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。 分层并查集经典例题：P2024 [NOI2001] 食物链。 最大匹配：匈牙利算法 模版：P3386 …

基础数据结构（前缀和/差分/树状数组/线段树） 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。 例如二维前缀和求法： 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题：NC225630 智乃酱的…

fhq_treap（无旋 treap） 参考：远航之曲的博客。 感觉比较意识流。 核心思想是平衡树分裂和合并。 类似于 Splay 把区间分离出来，fhq_treap 可以把平衡树进行分裂来提取需要的区间，再通过合并平衡树来维持树高（即堆性质）。这样不仅可以做到维护区间，还免去了旋转操作，代码较为简单。 split & merge &…

在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法，更推荐类似于 Dinic 的 spfa+dfs 的写法，详见最下方的“附加代码”部分。 MCMF（基于 spfa 实现） 模板题：Luogu3381。 即给定一张网络，每条边都有一个权值和流量限度，这条边上每有一个流量，总费用就加上这个权值，你需要在…

块状链表 参考：Tak_vin 的 博客 及相关代码。 这篇可能写的巨草，主要是给我自己看的。 一种根号数据结构，支持一个区间的动态插入和随时访问。 以 Luogu4008 [NOI2003] 文本编辑器 为例。 题意： 维护一个文本编辑器，支持： Move/Prev/Next 移动光标位置 Insert 在光标处插入若干个字符 Delete 删除…

参考：p_z_y 的博客，YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题：CF600E Lomsat gelral。 题意： 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…

第一道题 CF1515I Phoenix and Diamonds 题目链接。 题意（5s,1000MB）： $n$​ 种钻石，一颗第 $i$​ 种钻石重量为 $w_i$​，价值为 $v_i$​，一开始第 $i$​ 中钻石的库存为 $a_i$​。接下来进行 $m$​​ 次操作： 1 k d：进货了 $k$ 个种类为 $d$ 的钻石； 2 k d：卖…

参考：泥土笨笨的博客，Leap_Frog 的博客。 好久没写学习笔记了啊…… 珂朵莉树 模板：CF896C Willem, Chtholly and Seniorious。 题意： 给定一个序列，支持区间加，区间赋值，询问区间第 $k$ 小，区间幂次和（即 $x$ 次方的和，取模）。 数据范围 $10^5$，数据随机。 珂朵莉树（Chtholly …

引用/参考：绍兴一中相关课件，Acfboy 的博客。 决策单调性 决策单调性指的是 dp 的决策时的最优位置是单调的。 常见地，若存在： $dp_i = f(dp_j)$ 中，$i$ 的决策位置是 $pos_i$，那么对于所有 $i\ge2,pos_i \ge pos_{i-1}$。 难点在于观察(猜)出其为决策单调，经常可以不证明。一般通过打表观…