[CF587F] Duff is Mad

fail 数上的子树更改或查询是易于维护的，而对一个字符串在 AC 自动机上经过的路径进行更改或查询只能暴力做。

所以如果直接把 CF547E 的做法用到这里来，区间询问拆成前缀，对每个前缀按顺序处理，fail 树上子树加，每个询问在 AC 自动机上暴力求和，时间复杂度为 $O(A\sum|s_i|+B\sum|s_{t_i}|)$。其中 $t_i$ 为第 $i$ 次询问的文本串，$A$ 为区间加的时间复杂度，$B$ 为单点查询的时间复杂度。注意式子中第一个 $\sum$ 是有约束的（不超过 $10^5$），而第二个没有。这样我们就获得了一个与文本串串长相关的暴力做法。

注意到第一个做法的问题在于遍历文本串的次数过多。如果选择每个文本串只进行一次遍历，对经过的所有点做 $O(1)$ 子树加（树上前缀和），然后依此处理该文本串相关的所有询问，这个做法的时间复杂度为 $O(\sum|s_{t_i}|+|t|\sum|s_i|)$，$t$ 为询问的文本串序列。

于是我们根号分治：对于长度不超过 $\sqrt{\sum|s_i|}$ 的串使用第一种算法，使用 $A=O(\sqrt n),B=O(1)$ 分块进行区间加单点查；否则使用第二种算法，此时 $|t|=O(\sqrt{\sum|s_i|})$。总时间复杂度为 $O((\sum|s_i|)^{1.5})$