ACAM
1.CF587F
题意
给n个字符串 \(s_1,s_2,\dots,s_n\)，有 \(|s_1|+|s_2|+\dots+|s_n|=L\)，每次给出三元组 \((l, r, k)\)，询问 \(\sum_{i=l}^{r}{occur(s_i, s_k)}\)，\(occur(a, b)\) 表示串a在串b中的出现次数
\(n,m,L\le10^5\)
题解
按B对字符串大小分类。当 \(|s_k|>B\)：考虑对于这样的 \(k\)，预处理出 \(occur(s_i,s_k)\)，在 ACAM 上的 \(fail\) 树上进行 \(|s_k|\) 次到根的链加法，可以 \(O(L)\) 解决，复杂度\(O(\frac{L^2}B)\)。
当 \(|sk|\le B\)：反过来，进行一个差分和扫描线，可以认为 \(O(n)\) 对 \(fail\) 树的子树进行区间加法，\(m\cdot B\) 次查询单点值，复杂度 \(O(nL^\epsilon+mB)\)。
视 \(n, m, L\) 同阶，总的复杂度 \(O(L^\frac32)\)，离线后注意好分开处理空间线性。
字符串出现次数 -> ACAM \(fail\) 树。