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

提供一个巨大复杂的场内做法。

由于允许 R_i 为空，所以对于子串 T_{[l, r]}，记 k' 为其至少需要多少个好的字符串拼接而成，则 \forall k \in [k', K]，(l, r, k) 均为好的三元组。

考虑贪心求解 k'：记 T_{[i, |T|]} 与 n 个串的 \text{lcp} 的最大值为 p_i，从 l 开始每次跳最远的右端点即可求解。

具体地，记 ans_{l, i} 表示 T_{[l, i]} 对应的 k'。为了对于一个左端点 l 求出所有 [l, r] 的 ans，考虑维护一个 t，初始为 l - 1，每次在 [l, t + 1] 范围内取一个 i，最大化 q = i + p_i，然后令 ans_{l, [t + 1, q - 1]} \gets \text{steps}，再令 t \gets q - 1，其中 \text{steps} 为操作次数，如果 q - 1 \leq t 那么提前终止，否则在 q = |T| + 1 时终止。

容易发现从初始状态跳跃一次之后，剩余的问题是一个几乎独立的子问题。形式化地讲，先判掉两种边界情况，第一种是 l + p_l = |T| + 1 的情况，此时有 ans_{l, *} = 1，第二种是 p_l = 0 的情况，此时不妨令 ans_{l, *} = K + 1。对于一般情况，我们求出一个 i \in [l + 1, l + p_l]，最大化 i + p_i（多个任取其一），那么可以用下述方式计算 ans 序列：

• 令 ans_{l, j} \gets \min(ans_{i, j} + 1, K + 1), j \geq i。
• 然后令 ans_{l, j} \gets 1, l \leq j < l + p_l。

为了更有利于后续处理，我们将这个过程精细化一点：

• 显然 ans 序列是不降的，记 x 为最小的位置满足 ans_{i, x} = K + 1，若没有则为 |T| + 1。假定 ans 序列初始全 0。
• 令 ans_{l, j} \gets ans_{i, j}, j \geq i。
• 对 ans_{l, [l, i - 1]} 加 1。
• 对 ans_{l, [l + p_l, x - 1]} 加 1，如果 l + p_l \leq x - 1。

这意味着，我们只需要支持将 ans_l 继承 ans_i，以及区间加两种操作，很难不想到用线段树处理。乍一看继承操作得用主席树，但是事实上我们可以把继承操作建树，从而离线处理掉。

具体来说，对于每个“ans_l 继承 ans_i”的操作，我们连一条 i \to l 的边，这样我们可以得到一个森林。考虑从根结点开始 dfs，每进入一个点时，我们分两种情况讨论：

• 点是根结点：这对应了上文 ans_{l, *} = 1 或 ans_{l, *} = K + 1 的情况，直接在线段树上对区间 [l, |T|] 区间加 1/K + 1 即可。
• 否则：线段树二分出上文中的 x，然后对 [l, i - 1] 与 [l + p_l, x - 1] 区间加 1 即可。

当我们从一个点回溯时，只需要撤销加入时的贡献即可。这样一来我们可以做到 \Theta(|T| \log |T|) 求出所有 ans。

考虑统计答案。统计好的三元组数量是容易的，对于每个 l 合法的三元组数为 \sum \limits_{r \geq l} (K + 1 - ans_{l, r}) = (|T| - l + 1)(K + 1) - \sum \limits_{r \geq l} ans_{l, r}，而 \sum ans_{l, r} 容易用线段树求出。对所有 l 的答案求和即可。

第二问会棘手一些，考虑将 l \leq i \leq r 这一限制容斥，即总三元组数减去 [l, r] \subseteq [1, i - 1] 的三元组数，再减去 [l, r] \subseteq [i + 1, |T|] 的三元组数。