Day 6。
好神奇的题啊，我完全不会做。
建出 \(s_1,s_2,\cdots, s_n\) 的 ACAM。
考虑在 \(r\) 处统计满足条件的数对 \((l,r)\) 的贡献。那么需要求出 \(f_r\) 表示文本串以 \(r\) 为结尾的前缀 \([1,r]\) 中，其所有后缀中模式串的出现次数。即：
\(l_i\) 表示第 \(i\) 个文本串即 \(s_i\) 的大小。
考虑询问 \([a,b]\)，\(\sum\limits_{i=a}^bf_i\) 表示的是所有 \(r\) 在 \([a,b]\) 之间的串的个数，缺少对 \(l\) 的限制。实际上，我们要求 \(l\in[a,b]\)。由于现满足 \(r\le b\) 且 \(l\le r\)，只需要满足 \(l\ge a\) 即可。
哪些 \(r\) 的贡献是正确的呢？若满足 \(r\) 为后缀的最长匹配到的文本串的 \(l\) 要 \(\ge a\)，那么 \(f_r\) 就正确地贡献到了答案里面。形式化地，记 \(g_r\) 为文本串前缀 \([1,r]\) 的后缀中匹配的最长模式串编号，即：
显然地，\(f,g\) 都能够通过 ACAM 处理出，如果找到最大的 \(p\) 满足 \(p-|s_{g_p}|+1< a\)，\(r\in[p+1,b]\) 的贡献就能直接通过 \(f\) 的前缀和求出。
对于 \(r\in [a,p]\) 的贡献呢？画图理解，实际上只需要求出 \(s_{g_p}[a:p]\) 这个子串里面文本串的出现次数即可。考虑如何对每个串 \(s_i\)，预处理出其长度为 \(j\) 的后缀中包含的文本串 \(c_{i,j}\)，直接对文本串的反串建 ACAM 即可。
如何找到最大的 \(p\) 呢？考虑二分。如果使用 \(O(1)\) RMQ，预处理 \(O(|t|\log |t|)\) 的话可能会很慢，除非你用四毛子，但是众所周知四毛子常数巨大。可以线段树上二分，复杂度 \(O(|t|)-O(\log |t|)\)。
于是我们就在 \(O(|t|+m\log |t|+\sum|s_i|)\) 的复杂度内被这题解决了。