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

一只绝帆 · 2025-01-11 11:52:44 · 题解

本题存在线性做法，即与输入量同阶，在保证其他范围的前提下 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 的点数，只需维护深度数组前缀和，递归子树前减一下，递归子树后加一下，前缀和可以在更新点值的时候动态更新（也可以给祖先打差分标记，回溯的时候对标记前缀和）。