P11291
dp 优化题，需要发掘一下转移的性质。
令 n=|T|。首先将字符串的限制转化掉，可以使用二分哈希的方法处理出 t[i:n] 与某个 S_i 的 \text{lcp}，我们显然只关心 \max，令这个最大值为 g_i，那么就要求如果以 i 开头，那么这个 R 的结尾必须落在 [i,i+g_i) 之中。先考虑如何判定合法，从前缀匹配是存在后效性的，但是可以转换维度，从后缀开始消。先考虑 70 分做法（我的赛时做法）：注意到对于一个固定的 l,k，合法的 r 是一段前缀，因此可以定义域值域互换，维护 f_{k,l} 表示对于固定的 k,l，最大的 r 使得 (l,r,k) 合法。转移考虑枚举 k 然后从 f_{*,k-1} 进行转移，可以倒序枚举 i 从 n 到 1，然后树状数组维护 [i,i+g_i) 中最大的 f_{*,k-1}，可以做到 \mathcal O(nk\log n)，第二问可以在此过程中维护区间加一次函数，进行离线并使用二次差分维护。
一个废话是 f 的具体值一定是某个 i+g_i-1 的值，对于 f_{l,k} 我们将这个 i 记作 R_{l,k}（R 是单词 \text{Real} 的简写，与题面中的 R 没有任何关系），即 f_{l,k}=g_{R_{l,k}}。考虑对这个 dp 进行优化，对于 k 很大时我们显然无法直接求，考虑发掘一下转移的性质，一个事情是你可以将 f 视为线段拓展一样的东西，就是要求从 l 拓展 k 次，每次拓展的左端点必须落在当前已有区间之中。显然你每次都会去贪心选取最优的转移点（即 j+g_j 最大的点），一个结论就是，在不考虑无法拓展时，每次选取的位置一定在新拓展的部分之中。证明是显然的，如果不在，在本次拓展你会直接选取这个点而不是在下一次拓展再选取。首先有 R_{i,1}=i，其次考虑 [i,i+g_i) 中的最大值位置 p，那么就一定对于任意 k 有 R_{i,k}=R_{p,k-1}，因为你其实可以看成是在左边拓展这个线段。
此时 k 的具体值是无用的，我们只关心从 i 开始不断跳 p 跳 k 次可以跳到哪里，不难想到建立边 i\to p，此时这张图在不考虑根的自环时是个森林。R_{i,k} 即为 i 的 \min(\text{dep}_i,k) 级祖先。第一问就是对到 k 级祖先的路径的 g_{i} 进行求和，由于 k 是固定的，所以容易拆贡献进行一些分讨维护。第二问就是考虑在暴力时你会进行二次差分的修改，具体而言你会对于 x\in[l,r] 加上一个函数 y=(r-l+1)-(x-l)，你会对二阶差分的数组进行四次单点修改。在前缀和意义也是容易维护的。时间复杂度 \mathcal O(n\log n+nm\log n)。