一定要会 trie，不一定要会 kmp。 作者是个 fw，有些话不是很标准，还请见谅。 为了方便，接下来的 acam，没有特殊表明，均表示 AC自动机。 我们直接引入一道题目 P5357。 这题就是标准的模板，从中，我们可以得到 AC 的作用：统计文本串内各个模式串的个数。 我们回忆一下 trie 的作用：判断一个字符串在不在一堆字符串里。 这和题目很像，我们想想怎么建这棵 trie。 我们...

我们有这样一个问题：修改点权，询问链上的点权和。这明显是个树链剖分模版。
但如果还有这些操作呢：断开一条边，连上一条边，保证一直是森林。这就是动态树的一种问题。
而 LCT 就是解决这些问题的优秀数据结构。

普通最大流的实现与一些例题。

题目链接：HDU5828 rikka with sequece 简要题面：实现 333 中操作：区间开根，区间加，区间求和。 如果直接暴力递归，区间加操作会破坏复杂度，例如交替的 2,32, 32,3 序列，我们反复做全局 +6+6+6，再开根，单次复杂度就变成 O(n)O(n)O(n) 了。 所以我们不能完全暴力，要单独维护一下懒标记。 注意到，有很多数开根后答案相同，比如 161616 ...

luogu 阅读链接。 题目链接。 题目的边用的是倍数关系（偏序）。 当 x→y,y→zx \rarr y, y \rarr zx→y,y→z，就必然有 x→zx \rarr zx→z。 为了避免这种情况，意味着每个点要么只有因数，要么只有倍数。 我们将每个点拆成两个点，x0x_0x0​ 表示图中 xxx 只能保留其的因数，x1x_1x1​ 表示其倍数。 再用一条边 (x,y)(x, y)(...

替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。

treap = tree + heap，就比 BST 多了几行代码。

平衡思路超简单，最早发明的自平衡二叉树，也是查询速度最快的平衡树，

luogu 阅读链接。 定义 BST（二叉搜索树）是一种树形结构，有如下性质。 空树是二叉搜索树。 若左子树非空，那么左子树上所有点的权值均小于其根节点的值。 若左子树非空，那么其右子树上所有点的权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 操作 BST 的单次操作最坏为 O(n)O(n)O(n)，nnn 表示 BST 内的节点数，即树的形态是一条链。 节点定义 ...

前言 本文的线性基指异或线性基。 由于作者太菜了本文的语言不会特别规范。 简介 线性基简称基，它是一个数的集合，并且每个序列都拥有至少一个线性基。 线性基有三个性质： 线性基中的几个数异或后不能得到 000。 线性基中的数在异或后能得到原序列中的所有数。 线性基在保证前两个性质时，会使得基内的个数最少。 基本操作 我们用数组 ppp 表示 {ai−1}\{a_{i - 1}\}{a...