sol CF587F AC 自动机 根号分治

注意下文中 fail 树和 trie 树的不同。

考虑给询问离线，然后差分成 \([1,r]-[1,l-1]\) 的前缀询问来做。

先对于 \(s_{1\dots n}\) 建立 AC 自动机。从左到右扫描询问，当扫描到 \(i\) 时就对 fail 树上的子树 \(i\) 全体 \(+1\)，使用树状数组维护即可。

答案即为 \(s_k\) 在 trie 树里链上的点权和。但是每次扫一遍链代价太大。注意到对于所有 \(s_k\)，其在 trie 树上的链是固定的，又有长度和固定的性质，不妨考虑根号分治。

• 当 \(|s_k|\leq B\)，直接暴力扫链即可。

• 当 \(|s_k|>B\)，注意到长度和固定最多有 \(\dfrac{n}{B}\) 个这种串，不妨直接预处理出所有的链，每次子树加时对每个串算贡献。

得到了时间复杂度 \(O(nB\log n+\dfrac{n^2}{B})\)，空间复杂度 \(O(\dfrac{n^2}{B})\)。由于这个 log 是树状数组的，所以没有什么优化的必要。

Code。

总结：长度和固定（或是维护出现次数这种经典的问题），且数据不好维护的情况下可以考虑根号分治。