斜率优化与例题。

P2617 单点修改，区间查询第 kkk 小。 树套树 区间第 kkk 小的一种解法是用主席树，利用两个子树做差实现。 但加上单点修改后，直接做每次修改是 O(nlog⁡n)O(n\log n)O(nlogn) 的，复杂度太大。 考虑平衡询问和修改的复杂度。 我们在主席树外套一棵树状数组。 询问时把两个子树作差变成 log⁡n\log nlogn 个子树作差。 修改时只需要修改 log⁡n...

用 FFT 实现多项式乘法

Gym-102465k Dishonest Driver 给出一个字符串，两个相邻且相同子串可以进行压缩，问压缩后字符串最少有多少字符，n≤700n \le 700n≤700。 将两个相邻区间合并，且 nnn 很小，就很像是区间 DP。 定义 dpi,jdp_{i, j}dpi,j​ 表示 [i,j][i, j][i,j] 的压缩后最少字符数。 显然有两种合并，直接拼起来相加，或者将右区...

$\mu$ 的定义，性质，和几道例题。

邮局 加强版 加强加强版 普通版 dpi,k=min⁡j=0i−1dpj,k−1+w(j+1,i)dp_{i, k} = \min_{j=0}^{i-1}dp_{j, k - 1} + w(j + 1, i)dpi,k​=minj=0i−1​dpj,k−1​+w(j+1,i) 其中 dpi,kdp_{i, k}dpi,k​ 表示前 iii 个放 kkk 个邮局的最小代价，w(l,r)w(l...

一定要会 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)(...