#x1026. CF547E Mike and Friends

    ID: 6077 远端评测题 3000ms 256MiB 尝试: 5 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-AC 自动机fail 树统计子树转区间树状数组离线查询一维前缀和2800

CF547E Mike and Friends

题目描述

有 nn 位乐队成员,第 ii 位的电话号码是字符串 sis_i。不同成员可以有相同的电话号码。

第 ii 位成员会拨打自己号码的每个连续子串。第 kk 位成员收到来自第 ii 位成员的电话次数,等于 sks_k 在 sis_i 中的出现次数。每个符合条件的起始位置计一次,出现位置可以重叠。

有 qq 次询问。每次给出 l,r,kl,r,k,求第 kk 位成员从编号在 [l,r][l,r] 内的成员那里收到的电话总数,即

∑i=lroccur⁡(sk,si).\sum_{i=l}^{r}\operatorname{occur}(s_k,s_i).

输入格式

第一行两个整数 n,qn,q(1≤n≤2⋅1051\le n\le2\cdot10^5,1≤q≤5⋅1051\le q\le5\cdot10^5)。

接下来 nn 行,第 ii 行给出由小写英文字母组成的非空字符串 sis_i,满足 ∑i=1n∣si∣≤2⋅105\sum_{i=1}^n |s_i|\le2\cdot10^5。

接下来 qq 行,每行三个整数 l,r,kl,r,k,满足 1≤l≤r≤n1\le l\le r\le n、1≤k≤n1\le k\le n。

输出格式

按询问顺序,每行输出一个整数。

样例

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5
7
5
6
3
6

Codeforces 原题 CF547E