询问等价于 \(s_{l,...,r}\) fail 树上最终节点子树加，求 \(s\) 在 fail 树上所有点上的权值和。
区间询问，每次都跑一遍 \(O(q(n\log S+len\log S))\)，\(len\) 为询问串的长度，\(S=\sum|s|\)。
离线下来扫描线，将 \(ans_{[l,r]}\) 拆成 \(ans_{[1,r]}-ans_{1,l-1}\) 优化到 \(O(n\log S+qS\log S)\)。
考虑根号分治，对所有 \(|s|\ge \sqrt S\) 的串直接预处理出所有 \(ans_{[1,i]}\) 预处理每个串复杂度为 \(O(n\log S+len\log S)\)。总复杂度 \(O(n\log S+nS\log S)\)。
同一个串在 fail 树上的节点数有限，每次对每个点询问浪费了子树加很多信息。
对每一个串分开处理。
每次询问的点都是一样的，考虑将这些点的权值设为 \(1\)，每个字符串对答案的贡献即为最终节点子树权值和。而子树权值和直接 \(O(S)\) 预处理，能将复杂度降为 \(O(S+n)\)。
而这种串个数为 \(O(\sqrt S)\) 量级的，总复杂度 \(O((S+n)\sqrt S)\)。
剩下的按照原本的做法即可，复杂度 \(O(n\log S+q\sqrt S\log S)\)。
总复杂度 \(O((s+n)\sqrt S+n\log S+q\sqrt S \log S)\)。大概是 5e8 量级。
Takanashi Rikka
// Problem: CF587F Duff is Mad
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF587F
// Memory Limit: 250 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define l(x) (x).size()
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=1e5+5;
#define int ll
int lst[N],ct,siz[N],t[N][26],tot=1,f[N],tr[N],ed[N],ans[N],dfn[N],d[N];
string S[N];
vector<int>w,e[N],s[N];
vector<pii>q[N];
int add(string s){int u=1;for(int i=0,p;i<l(s);u=t[u][p],i++)if(!t[u][p=(s[i]-'a')])t[u][p]=++tot,lst[tot]=u;return u;
}
void build(){queue<int>dl;for(int i=0;i<26;i++)if(t[1][i])f[t[1][i]]=1,dl.push(t[1][i]);else t[1][i]=1;while(!dl.empty()){int u=dl.front();dl.pop();for(int i=0;i<26;i++)if(t[u][i])f[t[u][i]]=t[f[u]][i],dl.push(t[u][i]);else t[u][i]=t[f[u]][i];}
}
void add(int u,int d){for(;u<=tot;u+=lowbit(u))tr[u]+=d;}
int ask(int u){int res=0;for(;u;u-=lowbit(u))res+=tr[u];return res;}
void dfs(int u,int fa){dfn[u]=++ct,siz[u]=1;for(int v:e[u])if(v^fa)dfs(v,u),siz[u]+=siz[v];
}
int sz[N];
void dfs1(int u,int fa){for(int v:e[u])if(v^fa)dfs1(v,u),sz[u]+=sz[v];
}
void UesugiErii(){int n,m,L=0,B;cin>>n>>m;for(int i=1;i<=n;i++)cin>>S[i],ed[i]=add(S[i]),L+=l(S[i]);B=sqrt(L);for(int i=1;i<=n;i++)if(l(S[i])>=B)w.pb(i);for(int i=0;i<=n;i++)s[i].resize(l(w)+5);build();for(int i=1;i<=tot;i++)e[f[i]].pb(i);dfs(1,0);// for(int i=1;i<=tot;i++)// cout<<dfn[i]<<'\n';int c=0;for(int i:w){d[i]=++c,intz(sz,0);int u=ed[i];for(;u!=1;u=lst[u])sz[u]=1;dfs1(1,0);for(int id=1,j;id<=n;id++)j=ed[id],s[id][c]=s[id-1][c]+sz[ed[id]];}for(int l,r,k,_=1;_<=m;_++){cin>>l>>r>>k;if(l(S[k])>=B)ans[_]=s[r][d[k]]-s[l-1][d[k]];else q[l-1].pb(mp(_,-k)),q[r].pb(mp(_,k));}for(int id=1,i;id<=n;id++){i=ed[id],add(dfn[i],1),add(dfn[i]+siz[i],-1);for(pii j:q[id]){int p=j.se,res=1,sum=0;if(p<0)p=-p,res=-1;for(int u=ed[p];u!=1;u=lst[u])sum+=ask(dfn[u]);ans[j.fi]+=res*sum;}}for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
signed main(){//cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}