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

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

自来水厂到你家的水管网是一个复杂的有向图，每一节水管都有一个最大承载流量。
水厂不放水，你家就断水了。但是就算水厂拼命的往管网里面注水，你家收到的水流量也有上限（毕竟每根水管承载量有限）。
你想知道你最多能够拿到多少水，这就是一种最大流问题。

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...

luogu 阅读链接。 前言 麻将模拟器 调了一早上结果发现 DP 中的 jjj 写成 iii 了。 题目中的和牌距离基本和向听数差不多。 文中的面子指刻子和顺子的统称。 基础操作 定义 #define endl '\n' #define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a+...