笔记

二分图与网络流 学习笔记

本文于 2020.3.9 进行了全文更新。 本文包括了二分图与网络流的绝大部分重要知识点,限于篇幅和作者水平,本文省略了较多的证明过程和推导过程。 学习二分图与网络流,最重要的是大量的刷题。在更新时,作...

左偏树 学习笔记

左偏树是一种可并堆,具有堆的性质,同时支持快速合并。 定义和性质 对于一棵二叉树,定义一个节点的 $\mathrm{dist}$ 为这个点到它的子树中距离它最近的叶子的路径上的节点数。一个空节点的 $\mathrm{dist...

虚树 学习笔记

又是以前学过的知识...... 对于一类特殊的树上问题,虚树通常可以简化树的结构,从而降低时间复杂度。 概念 有这样一类树上数据结构题,每组询问会涉及树中若干个关键点,但所有询问涉及的关键点总数并不...

Lyndon 分解 学习笔记

一个很冷门的字符串算法 Lyndon 串 对于一个字符串,若其本身就是其最小后缀,则称它为 Lyndon 串。 形式化地,对于长度为 $n$ 的字符串 $s$,若满足对于 $i \in [2,n]$,都有 $s < s[i:n]$,则称其为 ...

Z 函数 学习笔记

Z 函数,又称扩展 KMP (exkmp),可以 $\mathcal O(n)$ 求出一个字符串的所有后缀与这个字符串的 LCP 长度。 定义 $z$ 函数 对于字符串 $s$,$z_i$ 定义为 $|\operatorname{LCP}(s, s[i:])|$,即从 $i$ 开始...

Prufer 序列 学习笔记

Prufer 序列是一种将带标号的树用一个唯一的整数序列表示的方法。 在本文中,我们要求树的节点数 $\ge 2$。 Prufer 序列 Prufer 序列可以将一个带标号 $n$ 个节点的树用 $[1,n]$ 中的 $n-2$ 个整数表示,...

平衡树学习笔记

其实是学过的,然后,就忘了...... 本文介绍 Splay/Link Cut Tree/FHQ Treap 三种平衡树相关的数据结构。 Splay Splay 是一种二叉查找树,它通过不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找...

多项式 学习笔记

唉,只能功利的学学了...... 多项式 长成 $$ f(x) = \sum_{i=0}^n f_ix^i $$ 这个鬼样子的式子就叫做多项式。 一般要求 $f_n \ne 0$,在这种情况下,$n$ 被称为多项式 $f(x)$ 的度,记作 $\operatorname{...

长链剖分 学习笔记

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

树上启发式合并 学习笔记

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