ZR B组 - 洛谷保存站

决定先在typora上写，回头传上来。
# Day1 DP优化和状态定义。

## 知识点：

四边形，斜率，wqs，二分栈/队列，状态定义（判定合法转状态，状态压缩），数据结构。

### 四边形/斜率/wqs

详情请见我的课件，可能重构。

### 二分栈/队列：

常用于 1D DP，转移形如 $f_i=\min f_j+w_{i,j}$ 的形式。

当相对靠后的决策点一定会被前面的决策点打败时（且败者永不翻身），使用二分栈，反之（仍然败者永不翻身）则使用二分队列。

以二分队列为例，二分栈类似。在二分队列中，我们需要维护保证队列中每个元素都对应着后面一段区间的转移，且后面的所有区间在当前都被覆盖。元素之间的转移区间无交。

维护队列中相邻元素更换决策的位置，所以要求题目的一维 DP 必须满足对于任意两个决策点，必须有分界点使得在这个分界点之前全部用一种决策点更优，而另一边用另一个决策点更优，因为这个性质，我们可以通过二分找到这个更换点，每次计算当前的 DP 值的时候，先把队首已经不是最优的（最优分界点在当前点前面）弹掉，然后用当前的队首计算出这个点的DP值。

在插入的时候，我们查看队尾与当前点和次队尾与队尾的分界点，如果前者小于后者，则当前的队尾一定是没用的，因为他的所有转移都被更优的覆盖了。弹掉继续此操作直至不满足条件。

二分栈同理，只需将上文中的队首队尾换做栈顶，区别是：在二分队列中，对于分界点前面的全部用下标靠前的转移过来更优，分界点后面用更大的。而在二分栈中，分界点前全用靠后下标的的转移。与二分队列恰相反。

在绝大多数题目中，二分队列更为常见，且常配合四边形不等式得到决策的单调性进行优化。将 $O(n^2)$ 优化至 $O(n\log n)$。

### 状态定义

纯 adhoc 部分，思维难度较大。有一类常用的套路流程：首先考虑结果状态的必要条件，将用于判定结果的信息作为数组下标进行计算。

尤其是一些方案内容及其复杂信息繁杂，但是判断合法的信息量不大，就可以使用这种方式，可以和贪心等算法联合，压缩状态的大小和数量。

这部分主打一个感觉，可能是是那种做的多了就自然而然想出来的部分。

## 题目：（题解待填坑）

### P6242及其弱化版
（四边形不等式，wqs，二分队列）

### loj6274
（状压 状压判定判定条件）

### uoj748
（贪心压条件）

### agc022E
（贪心压条件）

### uoj559 
（线段树合并维护转移）

### CF1416E
（集合维护解的连续段）

# Day2 字符串
## 知识点：
(ex)kmp，manacher，PAM，ACAM，SA，（广义）SAM，SuffixTreap。

### kmp
略。记一个神秘结论：串的border 构成 $O(\log)$ 个等差数列，没有听懂怎么用。

### exkmp
计算每一个后缀和整个串的 $lcp$ ，通过维护当前所有 $lcp$ 中最靠右的节点加速计算，跳过需要重复比对的部分。例如：当前后缀被包含在前面某一个后缀的 $lcp$ ，那么在这个 $lcp$ 部分，和一开始是一样的，可以直接将当前后缀的 $lcp$ 初值对应到整个串的最前面一部分，加速计算。

讨论一下可以得到只有当当前得到初值 $lcp$ 的右端点和当前最右右端点重合时会向右有扩展的可能。也就是每次向右扩展都会使最右端点向右。

由于串长限制，扩展次数均摊 $O(n)$。

### manacher 
和 exkmp 类似，维护最右端点，用已有信息加速计算，也是只有右端点和当前最右端点重合时会产生扩展的可能。

### ACAM
kmp在多串形势下的产物，维护了当前节点在多串情况下的最长 border 指向。用于多个模式串的匹配。复杂度可以摊到 $O(n)$ 。

在实际应用中，一般会转化为一种被称为 trie 图的东西，将没有下一步转移的边直接连向该字符跳 border 会到达的最终节点。复杂度更加直观不需要均摊也是对的。

计算每一个节点代表的字符串在文本串中出现的次数的时候，不能直接跳 border 给每个节点都加上，一般使用打 tag 的形式最后统一处理。

一个技巧是：如果 x 是 y 的子串，且都在 ACAM 被表达了。那么我们用所有节点及 fail 边建出 fail 树。一定存在的 trie 上 y 到根的路径上的节点在 x 的子树中（实际上出现的次数恰等于在 x 子树中的这种点的个数）。这个性质使得我们可以在 fail 树上操作，且大多是子树操作，可以通过 dfs 序排成序列的区间操作。

### PAM 
类似 trie 的一种结构，区别是维护了奇串和偶串两颗树，且每一个节点挂的都是真实串的一半（这样便于扩展）。fail 边记录当前代串的 border （显然也是回文串）。和 AC 自动机类似。但是目前应用范围不大，并不常见。绝大多数时候可以被 manacher 替代。

### SA
对一个串的所有后缀进行排序。可以解决子串问题。排序方式为：倍增加基排，每次只考虑每个后缀的前一部分。这样每次可以视作对若干二元组排序。维护两个数组：$sa_i$ 为排名为 $i$ 的后缀编号，$f_i$ 为编号为 $i$ 的后缀当前纳入了计算的部分的排名。
显然有编号为 $i$ 的后缀在进行下一次倍增时的第二关键字为 $f_{i+2^k}$（超出 $n$ 的部分补零）。按照第二关键字排序，按照第一关键字插桶。第一关键字的桶做前缀和，按照第二关键字遍历，对每个第一关键字位置维护有多少已经比这个小了（上一个位置的前缀和加上这个位置已经被占掉的部分），计算出新的 $sa$。进而继续算出新的 $f$。

### SAM
用不着，没特别透彻完全的听懂，不是很会用。将原串中所有出现位置右端点集合一直的子串压为一个节点，维护字符出边儿子作为转移，$link$ 维护以当前为后缀的

## 题目（题解待填坑）：

### P2414 （ACAM离线fail树上区间查）

### loj10059 （stack记录位置ACAM对应节点）

### P4287 (PAM or manacher+set)

### K-palindrome String （来源未知）（PAM fail树上维护栈内指针）

### P4762 （PAM上维护栈内指针，处理dp）

### loj2377 
（拆贡献，单调栈计算height数组的有贡献面积）

### loj2083 
（转化为前后缀枚举断点拼接，后对序列分段，利用正反两个SA计算前后缀需要的信息）

### Annihilate 
（luogu，还没找题号）（放在一起跑SA，记录SA每个点前不同串的最近的位置，维护lcp）

### loj2133 
（对height建出笛卡尔树或按照height顺序并查集）

后面除了板子全都不可做（雾）。

正在渲染内容...