虽然堆砌了很多高级数据结构……实际上做法是很 trivial 的（
所以也可以用 ACAM 做（
简单地建出广义 SAM 并记录每个串对应的状态，然后 Parent Tree 上线段树合并维护在每个串中的出现次数（即 \(\rm endpos\) 大小），区间查询即可。
隔壁 CF666E 的弱化版（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
using namespace std;
const int N = 2e5;
int n,q;
char s[N + 5];
int ed[N + 5];
namespace SEG
{
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int seg_tot;
void insert(int x,int &p,int tl,int tr)
{
int &tot = seg_tot;
!p && (p = ++tot),++seg[p].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
int &tot = seg_tot;
int p = ++tot;
seg[p].sum = seg[x].sum + seg[y].sum;
seg[p].ls = merge(seg[x].ls,seg[y].ls);
seg[p].rs = merge(seg[x].rs,seg[y].rs);
return p;
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
}
namespace SAM
{
struct node
{
int ch[26];
int fa,len,rt;
} sam[(N << 1) + 5];
int tot = 1,las = 1;
inline void insert(int x,int pos)
{
if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
{
SEG::insert(pos,sam[las = sam[las].ch[x]].rt,1,n);
return ;
}
int cur = las,p = ++tot,flag = 0,nxt;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
cur == las && (flag = 1),nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
SEG::insert(pos,sam[las = flag ? nxt : p].rt,1,n);
}
int c[N + 5],a[(N << 1) + 5];
inline void init()
{
for(register int i = 1;i <= tot;++i)
++c[sam[i].len];
for(register int i = 1;i <= N;++i)
c[i] += c[i - 1];
for(register int i = tot;i > 1;--i)
a[c[sam[i].len]--] = i;
for(register int i = tot;i > 1;--i)
sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(register int i = 1;i <= n;++i)
{
scanf("%s",s + 1),SAM::las = 1;
for(char *p = s + 1;*p;SAM::insert(*p++ - 'a',i));
ed[i] = SAM::las;
}
SAM::init();
for(int k,l,r;q;--q)
scanf("%d%d%d",&l,&r,&k),printf("%d\n",SEG::query(l,r,SAM::sam[ed[k]].rt,1,n));
}