本博客仅罗列定理，不给出证明，如需要请自行搜索。 质数相关 线性筛素数 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$（即子树大小）最大的那个。； 轻儿子：非重儿子的子节点； 重边：一个…

也只有我这种蒟蒻会现在才学平衡树吧…… 本博客参考：PoPoQQQ 和 nzhtl1477 的课件；do_while_true, hzwer, 皎月半洒花 和 yybyyb 的代码启发 其实“参考”也就是我本人在学习时使用的资料。 前置 - 二叉搜索树（BST） 模板题：Luogu5076 关键性质：一个节点 $x$ 左子树所有点的关键字都比 $x…

原来这篇博文放了一堆板子，后来发现一点用都没有，还不如直接在洛谷搜模板，于是就改造了一下，现在该博文会陆续放一些非板子的(或许)有用的内容，比较琐杂。 快读快写 手写快读 来源：青珹的博客 inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ …