2022寒假集训 - 游记 | Final Fantasy = xixike = 人间忽晚，山河已秋

# 点双，边双

（掌握较为熟练）

# 点双：

定义：删去一个点之后，图仍然联通，则称这个图是点双联通的。一个无向图里最大的点双联通子图称为点双连通分量。
算法：跑 Tarjan，回溯过程中若 $low_y \geq dfn_x$ 就出栈直到目标节点出栈，弹出的点为一个点双。

# 边双：

定义：类似于点双，只不过条件都改为边。
算法：同样和点双很像，如果有 $low_y > dfn_x$ 那么存在点双，弹栈加点即可。

# kmp & AC 自动机

（掌握熟练）

两者都是关于字符串匹配的算法。

不同在于 kmp 是单模式串，AC 自动机能够实现多模式串匹配。

# kmp

$border$ ：一个字符串除了它自己外最长前缀等于后缀的长度，例如 abccdscba 的 $border$ 为 3。
建 $nex$ 指针方法：
- 对于一个新的字符 $s_i$ ，令点 $j$ 暴力往前跳 $nxt$ ，并判断 $s_{j + 1}$ 是否等于 $s_i$ ，如果相等退出循环。
- 此时已经在循环外了，但我们可能有两种情况，第一个是 $j$ 已经跳到了 0，第二中是找到了一个 $j$ 使得 $s_{j + 1} = s_i$ ，所以我们判断一下 $s_i$ 是否等于 $s_{j + 1}$ ，如果相等，令 $j$ 加 1。
- 最后再给 $nxt_i$ 赋值为 $j$ 。

# AC 自动机

学习 AC 自动机前有必要了解一下 $trie$ 树。
$trie$ 树： $trie$ 树其实是一个多模式串的 $kmp$ ，我们设 $trie_{p, c}$ 表示 $p$ 这个节点后面是否有字符 $c$ 的链接。每次插入一个字符串 $s$ 时，从根节点往下跳找到 $trie$ 树与 $s$ 的最长公共前缀，这些前缀里的字符不必新建节点，然后对于 $s$ 后面的字符在 $trie$ 树上新建节点。
此时我们已经有了 $trie$ 树，但是总感觉还差点什么， $trie$ 树有什么用呢？没法快速查询到一个字符串你建出来这么一棵树也没啥用啊？
AC 自动机：AC 自动机的精髓在于 $fail$ 指针， $fail$ 指针类似于 $kmp$ 里的 $nxt$ 指针，只不过同样从链上变到了树上。
建 $fail$ $f a i l$ 指针：
- 我们利用广搜实现，先把所有串的首字母塞到队列里。
- 枚举 26 个字母 $c$ ，判断当前点 $p$ 是否有 $c$ 儿子，如果有，令 $trie[p][c]$ 的 $fail$ 指向 $p$ 的 $fail$ 的 $c$ 儿子，并令 $trie[p][c]$ 入队。
- 对于 $p$ 没有的 $c$ 儿子，我们可以顺便建出 $trie$ 图，反正你没有 $c$ 儿子，那我要你干嘛，直接令 $trie[p][c] = trie[fail[p]][c]$ 即可。
查询：比较简单了，直接在 $fail$ 树上乱跑即可。

# SA & SAM

（SA 只写过板子，SAM 写过部分题，掌握还可以）

# SA（Suffix Array）

一些变量的定义：
- $rk_i$ ：从 $i$ 开始的后缀在所有后缀中的排名（升序）。
- $sa_i$ ：排名为 $i$ 的后缀在原串中首字母的位置。
- $hei_i$ ：排名为 $i$ 的后缀和排名为 $i - 1$ 的后缀的 lcp（最长公共前缀）
  （后缀排序的模板不需要用 $hei_i$ ，但是在应用中经常用到）
一些性质：
- $rk[sa_i] = sa[rk_i] = i$
- $hei[rk_i] \geq hei[rk_{i - 1}] - 1$ （用于线性求 $hei_i$ ）
算法：倍增，基数排序
假设我们已经知道了长度为 $w$ 的字串排名 $rk_w[1..n]$ ，现在要求出长度为 $2w$ 的字串排名。
先取出所有长度为 $2w$ 的字串，然后按 $rk_w[i]$ 为第一关键字， $rk_w[i + w]$ 为第二关键字进行基数排序（基排其实就是有两个关键字的桶排，先对第一关键字进行桶排，排名相等的再按第二关键字桶排）
过程：对于两个分别以 $i,j$ 开头的长度为 $2w$ 的字串，我们先判断 $rk_w[i]$ 和 $rk_w[j]$ 的大小关系，如果相等，再判断 $rk_w[i + w]$ 和 $rk_w[j + w]$ 的大小关系。

# SAM（Suffix Automaton）

定义：后缀自动机，是一个包含字符串 $s$ 所有后缀的最小 DFA。
一些变量的定义：
- $endpos(t)$ ： $t$ 为 $s$ 的任意非空字串， $endpos(t)$ 表示 $t$ 在 $s$ 中所有结束位置的集合。
  所有 $endpos(t) = endpos(t')$ 的字串为一个等价类。
- $len_i$ ：表示第 $i$ 个等价类里面最长的字串长度。
- $par_i$ ：在由等价类包含关系形成的 $parent$ 树上， $i$ 节点的父亲。
在线构建：
- 把初始状态存到 $p$ 中，然后新建一个节点 $np$ ，令 $len_{np} = len_p + 1$
- 从 $p$ 开始，如果还没有到字符 $c$ 的转移，那么我们添加一个到 $np$ 的转移，遍历后缀链接，即跳到 $par_p$ ，如果找到了一个已经有转移的 $c$ ，那么退出循环。
- 如果没有找到这样的 $c$ ，令 $par_{np} = 1$ 并退出。
- 令 $q$ 为从 $p$ 能转移到那个 $c$ ，即 $ch[p][c]$ 。然后我们分两种情况， $len_p + 1 = len_q$ ，或者不等。
- 如果相等， $par_{np} = q$ 并退出。
- 如果不等，意味着 $np$ 应该在 $p$ 和 $q$ 之间，所以新建一个节点 $nq$ ，把 $q$ 的信息全部复制上去，令 $par_{nq} = p$ ， $par_{np} = par_{q} = nq$ 。

# Burnside 定理 & Polya 定理

（不太会）

# 点 / 边分治 & 树分治

# 点分治

（掌握熟练）

思路：每次找到树的重心，处理经过重心的路径，然后删掉重心，递归处理所有儿子。
复杂度证明：每次找到的都是树的重心，所以树的大小至少除以 2，最多递归 $\log$ 次。

# 边分治

（没写过题）

思路：与点分治非常像。每次删一条边，再递归处理。
但是这样对复杂度有一定影响，假设一张菊花图，复杂度就会退化为 $O(n^2)$ ，因此我们在处理时往往对树进行三度化，在有边权的情况下，我们还会进行二度化。

# 树分治（动态点分治）

即支持修改的点分治。
思路：我们要对原树建出一棵重构树，这棵重构树中把当前的重心向上一层的重心连边。
然后在这棵重构树上进行一系列操作。

# LCT

（会板子，一般要调好久）

本质：一个 splay 森林，每个 splay 维护原树中的一条链，splay 中序遍历为这个链由浅至深的顺序。
利用虚边把各个 splay 连起来，同时用来维护原树的结构。

# 网络流

（会板子，写过一些题，遇到比较难的建模还是不会）

# 最大流

dinic 算法：先跑一遍 bfs 对图分层，然后 dfs 找增广路。bfs 可以帮助我们判断是否还有到汇点的增广路，以及保证我们找到的增广路时最短的。
找增广路的过程中令正向边减去流量，反向边加上流量。
两个优化：
- 多路增广：每次找增广路时，把当前边的残余流量全部用完，即对于当前边多次增广。
- 当前弧优化：如果一条边已经被增广过，那么它不可能再被增广，所以下次增广的时候不必再遍历那些边。

# 最小割

最小割 = 最大流

# 最小费用最大流

魔改一下最大流即可。
把最大流中的 bfs 改为按 $cost$ 跑 spfa，然后再 dfs 找增广路。

# 斜率优化

（掌握还行，比较简单的斜率优化式子可以自己推出来）

# 四边形不等式

（比较简单的式子可以自己推出来）

~~我们知道~~，四边形不等式需要满足如下条件：

$w(a, c) + w(b, d) \leq w(a, d) + w(b, c)\ \ (a \leq b \leq c \leq d)$

同时，我们知道只需要证明

$w(i, j) + w(i + 1, j + 1) \leq w(i, j + 1) + w(i + 1, j)$

即可证明上述条件。

那么这个性质有什么用呢？

~~众所周知~~，拥有了这个性质之后我们就有了决策单调性，也就是 $p_{i, j - 1} \leq k \leq p_{i + 1, j}$ 。

$p_{i, j}$ 是转移到 $dp_{i, j}$ 时的最优决策点，就是上面转移方程里使得 $dp_{i, j}$ 取最优值时转移过来的那个 $k$ 。

所以我们在对 $dp_{i, j}$ 进行转移时只需要枚举 $p_{i, j - 1} \sim p_{i + 1, j}$ 即可。

# WQS 二分

（写过一些题）

WQS 二分也叫带权二分，主要解决一类凸包上的问题。

假设当前你有一个很难计算的凸函数 $f(x)$ ，此时你要计算一个指定的 $f(n)$ ，但是由于一些奇奇怪怪的限制条件，我们没办法如在题目要求时间内计算出来，何快速求出呢？

我们可以二分一个斜率 $k$ ，然后计算斜率为 $k$ 的一条直线落到这个凸壳上时的交点。

设这个交点为 $(x,f(x))$ ，再设函数 $g(k)$ 表示表示斜率为 $k$ 的直线落到凸壳上时的截距。

那么：

$f(x)=g(k)+kx\\ g(k) = f(x) - kx$

由于 $g(k)$ 是一条直线，感性理解一下，我们在计算这条直线上的值时就不需要考虑原题中的限制条件了。

于是我们就可以通过二分斜率来快速的找出答案了。