题解：P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2

本题存在线性做法，即与输入量同阶，在保证其他范围的前提下 $n$ 可以开到任意大。

首先来刻画结构，我们发现可以贪心求解，从 $l$ 往右跳 $\rm lcp$，这一段贡献是 $K$，然后不断将 $r$ 设为区间 $\max$，贡献逐级递减，这样我们就会了平方算法，第二问只需区间加等差数列。

求解 $\rm lcp$ 时，我们使用广义 $\rm SAM$，把所有串的反串都扔进去，把所有属于 $S$ 前缀都标记上（即每个 $S$ 插入的最后一个节点的所有祖先），标记的节点的 $\rm len$ 对子树取 $\max$。

考虑将跳的过程连成森林，每个点连向他第二步的“跳板”，则我们求的是祖孙链贡献。

形式化地讲，我们设第 $i$ 个位置一步能覆盖到 $r_i-1$，则令 $k_i=\text{argmax}\{ r_j\mid j\in[i,r_i]\}$，我们 $i\to k_i$，令这条边的边权是 $r_{k_i}-r_i$，则每个点作为 $l$ 的贡献是 链底点权 $\ K$ 加上 链上每条边的 $($边权 $\ ($边下方点的深度$))$ 减掉 链上每条边的边权和 $*\ ($链底点深度 $-K+1)$。

求解 $k_i$ 时，如果想要追求线性的复杂度，可以使用线性 $\rm RMQ$。

尝试解决第二问，考虑并不每段加每段的，而是求出单步可达、两步可达、三步可达等等的贡献，注意“单步可达”实质上意味着 $l$ 固定，$r\in[l,R]$。

所以这是公差为 $-1$ 的等差数列加，那么我们提前进行二阶差分（第一阶我们倒着差分），考虑一条距离 $\le K$ 的祖孙链 $(x,y),d_x\ge d_y$，贡献形式就变成了简单的 s2[x]++,s2[r[y]]--。

直接考虑 s2[x] 被加了多少次，以及 s2[r[y]] 被减了多少次即可，前一个是 dfs 栈，后一个是 dfs 子树，我们要询问子树内深度 $\ge x$ 的点数，只需维护深度数组前缀和，递归子树前减一下，递归子树后加一下，前缀和可以在更新点值的时候动态更新（也可以给祖先打差分标记，回溯的时候对标记前缀和）。