bzoj 3123
题意：小$Z$有一片森林，含有$N$个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有$M$条边。
小Z希望执行$T$个操作，操作有两类：

1. Q x y k查询点$x$到点$y$路径上所有的权值中，第$k$小的权值是多少。此操作保证点$x$和点$y$连通，同时这两个节点的路径上至少有$k$个点。
2. L x y在点$x$和点$y$之间连接一条边。保证完成此操作后，仍然是一片森林。

这题查询$k$小值点，显然主席树。
考虑怎么处理合并两棵树。我们想到了LCT。但是这题我们完全可以启发式合并。
每次合并两个集合，然后对小的集合重新算倍增、深度等
注意本题是合并的时候再建链，而不是先建链再合并，否则会合并很多次，造成数据重复

知识点：
1、加边要加双向边

BZOJ 3997
题意： 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

一开始觉得是上下界网络流。。范围太大了
这题是一个最小链覆盖问题，可以转化为最长反链覆盖。
考虑这里的反链，我们让$x$能到$y$看作偏序关系，然后对于$x,y$在同一反链当且仅当这两个点是右上、左下关系
那么设$dp(i,j)$为以$(i,j)$为左下角的矩形中的最长反链长。那么考虑转移
$$
dp(i,j)=\max(dp(i-1,j), dp(i,j+1), dp(i-1, j-1)+a_{i,j})
$$
前两个是继承关系，后一个是包含$(i,j)$的最长反链长，显然$(i,j)$和$(i-1, j-1)$在一个反链。

知识点
1、只向下/右：DP
2、二分图网络流问题：链、反链、最小点覆盖、最大独立集的转化

Bzoj 1143
题意：见上。

补充两个问题 (Luogu题面)

接下来一行输出一种可行的选取方案。对于每个岔口依次输出一个整数，如果在该岔口设置了祭祀点，那么输出一个$1$，否则输出一个$0$。应确保你输出的$1$的个数最多，且中间没有空格。 接下来一行输出，在选择最多祭祀点的前提下，每个岔口是否能够设置祭祀点。对于每个岔口依次输出一个整数，如果在该岔口能够设置祭祀点，那么输出一个$1$，否则输出一个$0$。

本题就是求一个最长反链。Dilworth定理转化为最小链覆盖。
然后二分图匹配求最小链覆盖(最大独立集)即可。
对于输出方案，可以取反最小点覆盖的方案，具体看算法竞赛进阶指南相关内容。
对于第三问，我们考虑枚举点，然后删掉这个点所有可以到达的点和删掉所有可以到达这个点的点，求一次最大独立集，如果少了1，则这个点是可以的。

4934 礼物
题意：$n$个$[0,2^k)$的数，分最少的组使得对于每个组的任意$a_1,a_2$, $a_1 \text{and} a_2 < \min(a_i,a_2)$，输出最少分组和一组方案。

首先将$a_1 \text{and} a_2 < \min(a_i,a_2)$转化，我们发现$a_1 \text{and} a_2$是不可能大于$\min(a_i,a_2)$的，所以这里就相当于只有等于的情况不成立。进一步分析可得，对于每个组的任意$a_1,a_2$，都不存在$a_1 \subseteq a_2$。

先介绍偏序：

偏序的定义
设$R$是集合$A$上的一个二元关系，若R满足：
1、自反性：对任意$x∈A$，有$xRx$；
2、反对称性（即反对称关系）：对任意$x,y∈A$，若$xRy$，且$yRx$，则$x=y$；
3、传递性：对任意$x, y,z∈A$，若$xRy$，且$yRz$，则$xRz$。
则称$R$为$A$上的偏序关系。
符号$≤$

具有偏序关系的集合$P$为偏序集，对应一个DAG图

严格偏序的定义
1、非自反性：$x ≮ x$
2、非对称性：若$x < y$, 则$y ≮ x$
3、传递性：若$x < y, y < z$, 则$x < y$

严格偏序也对应一个DAG图。但是不能使用Dilworth定理

Dilworth定理
在DAG图中
1、最小反链覆盖等于最长链长度等于拓扑序层次数：拓扑排序
2、最小链覆盖等于最长反链长度等于链的起点数：二分图
反链：在DAG图中不存在任意两个点是前驱后继关系的点集

将$a \subseteq b$看作一个偏序关系(题目保证$a_i$互不相同，则为集合)，然后建立一个 DAG 图，根据Dilworth定理，我们可以发现这里就是在求一个最小反链覆盖，那么求图的最长链即为答案。

注意本题的连边优化，若$u$到$v$有一条边，$v$到$w$有一条边，那么$u$到$w$的边是无意义的。所以我们每次连边只用连与当前状态二进制下1相差一位的。因为这样连就不会连出上面的$u$到$w$的边，并且将边的数量转到了$k \cdot 2^n$级别。

知识点：
1、Dilworth定理、偏序

Loj 2312
题意：给出一个 $n​$ 位随机 $01​$ 串，定义 $\text{data}(l,r)=\max(\text{LCP}(\text{Suf}_i,\text{Suf}_j)|i≠j,l≤i,j≤r)​$ 。
给出 $m​$ 个询问 $[l,r]​$ ，求
$$
\sum\limits_{i=l}^{r-1}\text{data}(i,r)
$$

题目说随机生成，那么估计LCP相同的概率为$({1\over 2})^{len} \cdot C^{2}_{r-l+1}$，在取$40$时，这个几率已经很小，我们直接对于每个后缀存前$40$个字符即可。考虑依次加入每个位置的后缀

我们发现对于一个区间$[l,r]$的答案，一定比$[l+1,r], [l+2,r], \dots , [r-1,r]$答案更大，因为他们是包含关系
那么我们可以运用这个单调性，还能发现答案是一块一块的，我们联想到数论分块的思想。

设$pos(i,j)$为$[1,i]$中后缀$\exists \text{LCP}=j$的最大位置。
那么求答案我们分成一块一块地求，具体看代码注释。

知识点：
1、单调性运用 (类似品酒大会从后往前求答案)
2、离线思想 (按某元素排序)

BZOJ 4566
题意：给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

一开始乱二分挂了……
其实这题就是Bzoj 3238 差异，我们可以想到连接两个字符串，中间用一个没出现过的字符连接，然后单调栈维护所有区间的最小值。但是这里是两个字符串，可能会有答案算到是同串的，那么我们考虑容斥。

即求三次后缀数组，第一次求连接串的答案，然后求两个原串的答案，最后用连接串答案减掉后面的两个原串答案即为最终答案，正确性显然。

知识点
1、多次求后缀数组，不要将思维局限
2、不要乱在height上二分

Bzoj 1212
题意：一段文章$T$是由若干小写字母构成。一个单词$W$也是由若干小写字母构成。一个字典$D$是若干个单词的集合。我们称一段文章T在某个字典$D$下是可以被理解的，是指如果文章$T$可以被分成若干部分，且每一个部分都是字典$D$中的单词。给定一个字典$D$，你的程序需要判断若干段文章在字典$D$下是否能够被理解。并给出其在字典$D$下能够被理解的最长前缀的位置。

容易发现若一个串$S$能被理解，那么$S+D_i$也能理解
那么我们就可以做一个存在性DP，按上面的来转移
我们发现单词长度不超过10，那么我们将单词插进Trie树，树高最高为10，那么直接暴力转移即可。具体可以看代码实现。

知识点：
1、数据范围小一定要重视
2、思路想好再写，不要贪快

BZOJ 3238
题意：给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求
$$
\sum_{i=1}^n \sum_{j=1}^{i-1} \text{len}(T_i) + \text{len}(T_j) - 2 \times \text{lcp}(T_i, T_j)
$$
其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

先将前面的求出来，等于$\frac{n(n+1)(n-1)}{2}​$, (可以分析一下合式组成或者将$j​$提取出来)

可以用艾佛森括号证明。
$$
\begin{aligned}
ans &= \sum_{i=1}^n\sum_{j=1}^i i+j \\
&= \sum_{i=1}^n\sum_{j=1}^n (i+j)[j > i] \\
&= \sum_{i=1}^n\sum_{j=1}^n i[j > i] + \sum_{i=1}^n\sum_{j=1}^n j[j > i] \\
&= \sum_{i=1}^ni(n-i) + \sum_{i=1}^n\sum_{j=1}^n i(i-1) \\
&= \sum_{i=1}^ni(n-i) + i(i-1) \\
&= (n-1)\sum_{i=1}^ni \\
&= (n-1)\frac{n(n+1)(n-1)}{2} \\
\end{aligned}
$$

考虑后面的$\text{lcp}(a,b)$，就是任意两个串的$\text{lcp}$的值。
求出后缀数组，则$[2,n]$上$height$的每个区间对答案贡献区间最小值。

而这里可以仿造Bzoj 4199，用并查集来做
下面考虑求每个区间最小值和的方法，这个是一个经典做法，即用单调栈解。
我们对于每个$i \in [2,n]$，求出$L_i, R_i$分别表示这个$i$位置能扩展到左右多少位置(即当前$i$的$height$值的扩展区域)
那么最后答案就是$\sum\limits_{i=2}^n (i - L_i)(R_i - i) $，即为区间端点在$i​$两端的方案。

考虑左边界怎么扩展，我们找到离$i$左边最近的$height_j \leq height_i$，则$L_i=j$
右边界即找到离$i$右边最近的$height_j \geq height_i$，则$R_i=j$

那么求单调栈维护这个就行了，单调栈维护的标志有上面加粗的关键字。具体可以看代码实现。注意处理一下边界状态。上面的可以画图更加清晰

知识点
1、求每个区间最小值和的方法：单调栈

BZOJ 4567
题意：给你$n$个字符串，不同的排列有不同的代价，代价按照如下方式计算（字符串$s$的位置为$x$）：
1.排在$s$后面的字符串有$s$的后缀，则代价为$n^2$；
2.排在$s$前面的字符串有$s$的后缀，且没有排在$s$后面的$s$的后缀，则代价为$x-y$（$y$为最后一个与$s$不相等的后缀的位置）；
3.$s$没有后缀，则代价为$x$。
求最小代价和。(吐槽一波题意)

显然第一种操作尽量少用($n^2$和$n$的增长级)，其实我们完全可以避免这种操作出现，即将他后缀权值安排在他前面。

那么我们将字符串翻转插进Trie，这样就可以维护后缀。
现在问题是Trie上有很多没有单词虚节点，不好处理，我们将其全部删掉，然后将有单词的数组成Trie 前缀关系树，那么这个树上孩子的最长前缀一定是父亲节点。

那么现在问题就是给每个点标号，然后让孩子节点减父亲节点的标号的差的总和最小。考虑将所有单词连接的虚点设为0，那么将这个虚点算作其中，然后将操作2转化到操作3。

那么我们现在可以考虑一个贪心，即从根开始DFS，每次找子树大小最小的进去然后DFS序是最优的。
具体证明比较困难，但是可以意会一下，即可以发现这样可以让后面的孩子的标号尽量小。

知识点
1、将字符串翻转插进Trie，这样就可以维护后缀。
2、将有单词的数组成Trie 前缀关系树

BZOJ 4199
题意：见上。

40分即枚举两个点Hash即可。
50分改为枚举长度+一个点，Hash即可。
考虑100分情况
我们发现两个答案都是都是递减的，所以我们可以逆向求答案。(后缀和过程)
这题显然是要用后缀数组了
我们将$height$值一样的存在一个vector里，然后按照$height$值倒着求答案。
附上样例一说明，SA后我们会得到如下的信息：

i    height    sa    stringsai asai
1    0        10    i          7
2    1        5    iiipoi      4
3    2        6    iipoi      8
4    1        7    ipoi      3
5    0        3    noiiipoi  4
6    0        9    oi          4
7    2        4    oiiipoi      7
8    1        2    onoiiipoi 1
9    0        8    poi          6
10    2        1    ponoiiipoi2

具体可以看xht 37 大佬的题解
这里直接讲并查集做法，即每次找一个位置，就把他和$SA$序上$i-1$位和$i$位的位置在并查集上合并，那么下次找的话，就可以直接统计两个连通块的信息。
并查集维护集合大小，集合最大值最小值(有负数存在，所以最大乘积可能来自最小值)，以上从上面的表格中可以分析出来

知识点

1、注意不要将SA的任何字符映射到0