土著神的信仰

· · 题解

考虑根号分治，设阈值为 B。

Case 1. |s|\le B

对于一个询问 (l,r,k)，记录 f_i 为 \operatorname{prefix}(s_k,i) 在 a_l\sim a_r 中的出现次数，g_i 为 \operatorname{suffix}(s_k,i) 在 a_l\sim a_r 的出现次数，则

ans=\sum\limits_{i=1}^{|s_k|-1}f_i g_{i+1}

差分一下，变成前缀对串的贡献。我们可以建立 AC 自动机，单点加子树求和。

可以用 \mathcal{O}(\sqrt{m})-\mathcal{O}(1) 的分块根号平衡复杂度。

总时间复杂度为 \mathcal{O}(qB+m\sqrt{m})。

Case 2. |s|>B

这个长度不允许我们对于单组询问解决时间复杂度带 |s|。

Solution 1

设 s_k=a+b，当 |a|\le B 或 |b|\le B 的时候可以像 Case 1 一样做。

当 |a|>B 且 |b|>B 时，它们所对应的字符串只有 \mathcal{O}(\frac{m}{B}) 种。

那么本质不同询问左端点 l 也只有 \mathcal{O}(\frac{m}{B})。

直接暴力计算每种本质不同询问的答案，复杂度是 \mathcal{O}(\frac{m^3}{B^2})。

取 B=n^{2/3} 得到最优复杂度 \mathcal{O}(n^{5/3})。

Solution 2

长度 >B 的字符串共 \mathcal{O}(\frac{m}{B}) 个。对于一个 k，我们预处理出 cnt_{i,j} 表示 \operatorname{prefix}(s_k,j) 在 s_i 中的出现次数。（后缀同理）

这一部分可以提前给每个串建立后缀自动机做到。

对于询问，使用**莫队**来解决。正确排序的莫队复杂度为 $\mathcal{O}(n\sqrt{q})$。 总复杂度相当于 $A_1+A_2+\cdots A_{\frac{m}{B}}=q,\max\{\sum \sqrt{A_i}\}$。 视 $q,m$ 同阶，可以证明 $A_i$ 取 $B$ 时最优，复杂度为 $\mathcal{O}(\frac{mn}{B}\sqrt{B})$。 取 $B=n^{2/3}$ 得到最优复杂度 $\mathcal{O}(n^{5/3})$。