有趣的思想
首先暴力的话，自然是对每一个询问在(AC)自动机上跑一遍(k)，看看跑出来的节点在(fail)树到根的路径上有多少个(l)到(r)之间的结束标记就好了
我们发现无论怎么优化好像都不是很可行，考虑一下对根号优化
对于长度大于(sqrt{n})的串，显然这样的串也不会超过(sqrt{n})个，我们把这些串在(AC)机上跑一遍，之后统计一下子树和，统计一个前缀和就可以回答询问了
这样复杂度是(O(nsqrt{n}))
对于长度小于(sqrt{n})的串，我们允许把每一个串都放到(AC)自动机上跑一遍，于是可以直接用主席树来查一下跑出来的节点到根有多少个标记在(l)到(r)之间
这边的复杂度是(O(nsqrt{n}logn))
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#define maxn 100005
#define M 4000005
#define re register
#define LL long long
#define int long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;}e[maxn];
struct Ask{int l,r,k,rk,o;}q[maxn];
int n,m,cnt,tot,num,sz;
int fail[maxn],son[maxn][26],len[maxn],head[maxn],a[maxn];
LL sum[maxn],pre[maxn],Ans[maxn];
int rt[maxn],ls[M],rs[M],d[M];
std::string S[maxn];
char T[maxn];
std::vector<int> v[maxn];
inline int cmp1(Ask A,Ask B) {if(A.o==B.o)return A.k<B.k;return A.o>B.o;}
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void work() {for(re int i=1;i<=n;i++) pre[i]=pre[i-1]+sum[a[i]];}
inline void ins(int i) {
scanf("%s",T);
S[i]=T;len[i]=S[i].size();tot+=len[i];
int now=0;
for(re int j=0;j<S[i].size();j++) {
if(!son[now][S[i][j]-'a']) son[now][S[i][j]-'a']=++cnt;
now=son[now][S[i][j]-'a'];
}
v[now].push_back(i);a[i]=now;
}
inline void Build() {
std::queue<int> q;
for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);
while(!q.empty()) {
int k=q.front();q.pop();
for(re int i=0;i<26;i++)
if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);
else son[k][i]=son[fail[k]][i];
}
}
inline int change(int pre,int x,int y,int pos) {
int root=++sz;
d[root]=d[pre]+1;
if(x==y) return root;
ls[root]=ls[pre],rs[root]=rs[pre];
int mid=x+y>>1;
if(pos<=mid) ls[root]=change(ls[pre],x,mid,pos);
else rs[root]=change(rs[pre],mid+1,y,pos);
return root;
}
inline int query(int p,int x,int y,int pos) {
if(!pos) return 0;
if(x==y) return d[p];
int mid=x+y>>1;
if(pos<=mid) return query(ls[p],x,mid,pos);
return d[ls[p]]+query(rs[p],mid+1,y,pos);
}
inline void Query(int i) {
int now=0;
for(re int j=0;j<len[i];j++)
now=son[now][S[i][j]-'a'],sum[now]++;
}
inline void dfs(int x) {
for(re int i=head[x];i;i=e[i].nxt) {
dfs(e[i].v),sum[x]+=sum[e[i].v];
}
}
inline void Dfs(int x) {
for(re int i=head[x];i;i=e[i].nxt) {
rt[e[i].v]=rt[x];
for(re int j=0;j<v[e[i].v].size();j++) rt[e[i].v]=change(rt[e[i].v],1,n,v[e[i].v][j]);
Dfs(e[i].v);
}
}
signed main() {
n=read(),m=read();
for(re int i=1;i<=n;i++) ins(i);
tot=std::sqrt(tot);Build();
for(re int i=1;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].k=read(),q[i].rk=i,q[i].o=(len[q[i].k]>tot);
std::sort(q+1,q+m+1,cmp1);
for(re int i=1;i<=cnt;i++) add(fail[i],i);
Dfs(0);
int L=1,R=1;Query(q[1].k);dfs(0),work();
for(re int i=2;i<=m+1;i++) {
if(len[q[i].k]<=tot) {for(re int j=L;j<i;j++) Ans[q[j].rk]=pre[q[j].r]-pre[q[j].l-1];R=i;break;}
if(q[i].k!=q[i-1].k) {
for(re int j=L;j<i;j++) Ans[q[j].rk]=pre[q[j].r]-pre[q[j].l-1];
memset(sum,0,sizeof(sum));
Query(q[i].k);dfs(0);work();L=i;
}
}
for(re int i=R;i<=m;i++) {
int now=0;
for(re int j=0;j<len[q[i].k];j++)
now=son[now][S[q[i].k][j]-'a'],Ans[q[i].rk]+=query(rt[now],1,n,q[i].r)-query(rt[now],1,n,q[i].l-1);
}
for(re int i=1;i<=m;i++) printf("%I64d
",Ans[i]);
return 0;
}