因为 SA 就很有用了，所以一直不想学 SAM。突然不知道为什么就想学了，可能是为了吊打兔兔吧。 后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。 直观上，SAM 可以理解为将字符串的所...

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

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

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

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

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

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)$。此外，长链剖分还有一些优秀的性质，目前长链剖分在信息学竞赛中应用很广泛。 定义 ...