Day 2

D 卡拉巴什的字符串

定义一个串的 LCP 集合，由每对后缀的 LCP 值组成。

给定一个母串，求它的每个前缀的这个集合的 mex。

考虑一个 endpos 等价类，如果它的出现位置不止一个，考虑某两个出现位置，它们的 LCP 为 $1$（必定存在，因为不存在的话与等价类定义不符），同时往左走一步，LCP 变成 $2$，一直到最大长度，都会出现。

因此答案必定是这样的结点的最大长度 $+1$。考虑这样的结点一定不是叶子结点，一定是一个内部结点，且根据后缀树的结构，内部不存在二度结点，因此只需要对所有内部节点取 $\max$ 即可。

注意特判：单字符集串，没有 $0$。

给定至多 $5 \cdot 10^5$ 个长度总和至多 $5 \cdot 10^5$ 的模板串，每个模板串有花费 $cost_i$。

要求将母串分为数段，每段均为模板串，产生的代价是该串的花费。

暴力：建出 AC 自动机，母串在 AC 自动机上跑，每次暴力跳 fail 指针转移 dp。

优化：暴力跳 fail 可能会退化为 $O(n^2)$，注意到几个事实：串长的种类小于 $\sqrt{5 \cdot 10^5}$，而每次跳 fail 串长至少减一，因此扣出有效的转移即可。

定义 $f(S,k)$ 表示将字符串 $S$ 划分为至多 $k$ 段，对于所有划分方案，要求最小化这种划分的字典序最大串。

每次询问一个后缀 $S[l \dots |S|]$，划分为至多 $k$ 段的答案，若有多种答案，输出左端点最小的，且它必须在某一种划分中。

大胆猜测：一定切在后缀的 Lyndon 分解上。

求出每个后缀的 Lyndon 分解，记这个 Lyndon 分解长度为 $p$，和这个 $$ 在后面一共重复了 $cnt$ 次，开始讨论：

后缀有一个整周期为 Lyndon 分解的长度，即类似 bbbbbb，我们肯定是尽量平均的划分，并且为了左端点最小，也就是取后缀的某几个周期的前缀。
$cnt$ 次 $p$ 后还有 Lyndon 分解，即类似 bbbba，如果 $cnt \bmod k = 0$，我们将 $cnt$ 次 $p$ 平均分解，答案为划分后最后一个段。
同情况 $2$，$cnt \bmod k \neq 0$，当成 $cnt + 1$ 段平均分解，答案为该后缀的前缀。

关于后两种情况的区别，如果整除的话，只将重复的 $cnt$ 段平均分解，那么答案就是最后一段，若你移动之前的某个分解位置，产生的字符串会大于这个最后一段（根据 Lyndon 分解）。其他情况就正常对所有段均分，取前缀即可。