参考：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}$。 难点在于观察(猜)出其为决策单调，经常可以不证明。一般通过打表观…

本博客仅罗列定理，不给出证明，如需要请自行搜索。 质数相关 线性筛素数 inline void sieve(int n){//线性筛求 pri 和 phi phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;} for(int j=1;j<=cnt&a…

本来没打算写这玩意儿，结果学习了之后觉得吉老师线段树真的很有意思，所以就决定简单写一下学习笔记。 本博客参考：echo 的 博客 与 代码启示，jiry_2 的 课件。 但是个人感觉该博客对于 pushdown 部分还是有点难以理解，所以决定用自己的语言写一篇博客阐述一下。 吉老师线段树 吉如一(jiry_2)的 PDF 见博客上方博客参考部分。 …

博客版本 参考：hsfzLZH1 的 博客 及代码启示 左偏树 模版题：Luogu3377。 由于朴素堆的合并操作可能会退化到 $O(n)$，所以我们需要通过一些方式维护合并操作，左偏树就是其中之一。 一些定义 该部分改编自 hsfzLZH1 的 博客 外结点 ：左儿子或右儿子是空结点的结点（首先左偏树是一个堆，堆是一棵二叉树）。 距离 ： 一个结…

博客参考：学委 的 博客 及 代码启示 暴力最大流 模板题：Luogu3376 在学习 Dinic 之前，必须先要知道暴力最大流的写法。 首先理解何为网络最大流。一张网络就是一张带权有向图，源点可以输出无限的流量，但是每一条边都有一个容量，需要满足这条边上的流量不能超出其容量（可以理解为输水系统），最后所有流量都会被汇点接收。我们需要求出这个网络运…

博客参考：CSDN 的 文章, enceladus, yybyyb, hyfhaha 的代码启示，皎月半洒花 的 博客, hyfhaha 的 博客。 前置知识 I - KMP字符串匹配 模版：Luogu3375。 我觉得这玩意儿比 trie 树难理解一点。 给定两个字符串 $s_1$ 和 $s_2$，我们需要求出 $s_2$ 在 $s_1$ 中所有…

这个算法还是比较容易理解的，只是代码调的我有点崩溃（还不是我太蒻了），因此学习笔记写的会比较简单。 本博客参考：PoPoQQQ 的课件；ChinHhh 的博客； attack 的代码启发。 前置 知识点：DFS序、线段树。 然后是一些概念： 重儿子：一个节点的子节点中，$size$（即子树大小）最大的那个。； 轻儿子：非重儿子的子节点； 重边：一个…