题意

有n只熊，从1到n进行编号。
第i只熊的电话号码是si。每只熊会给那些电话号码是他的子串的熊打电话（可能会给自己打）。
call(i, j) 表示第i只熊给第j只熊打电话的次数，也就是第j个串在第i个串中出现的次数。
迈克会有q次询问。每个询问中给出l,r,k,然后请您计算一下 ∑ri=lcall(i,k)

题解

这题想了一会就想出来了，感觉不难啊
这种东西考虑AC自动机就好了啊
建立fail树
每个节点可能有若干个值
然后问题转化为了询问一个子树里面，l~r里面所有数出现次数的中和
这个的话，我自认为想到了一个比较优秀的做法
拆成两个，答案是$1~r$的答案-$1~(l-1)$的答案
这个的话，分别按照r和l排序，做两次
每一次假如这个点，就暴力吧他所有链的状态++，这个的代价是长度总和
然后dfs序询问子树就可以了
时间复杂度$O(nlogn+qlogq)$
看大家T了这个多发，我这个很稳啊，只是一开始数组开小T了一发
CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int N=500005;
int n,q;
vector<char> ss[N];
struct qq
{int son[26],fail,c;
}tr[N];int tot=0,now;
int lalal[N];
void Ins (int x)
{if (tr[now].son[x]==0)  tr[now].son[x]=++tot;now=tr[now].son[x];
}
void get_fail ()
{queue<int> q;q.push(0);while (!q.empty()){int x=q.front();q.pop();for (int u=0;u<26;u++){int y=tr[x].son[u],f=tr[x].fail;if (y==0) {tr[x].son[u]=tr[f].son[u];continue;}if (x==0) tr[y].fail=0;else tr[y].fail=tr[f].son[u];q.push(y);}}
}
LL ans[N];
struct qt{
   int l,r,k,id;}s[N];
struct qy{
   int x,y,last;}e[N];int num,last[N];
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int L[N],R[N];
bool cmpr (qt x,qt y){
   return x.r<y.r;}
bool cmpl (qt x,qt y){
   return x.l<y.l;}
LL f[N];
int lb (int x){
   return x&(-x);}
void change (int x){
   while (x<=num){f[x]++;x+=lb(x);}}
int get (int x)
{int lalal=0;while (x>=1){lalal=lalal+f[x];x-=lb(x);}return lalal;
}
void solve1 ()
{memset(f,0,sizeof(f));sort(s+1,s+1+q,cmpr);int o=1;for (int u=1;u<=n;u++){int len=ss[u].size(),now=0;for (int i=0;i<len;i++){int x=ss[u][i]-'a';now=tr[now].son[x];change(L[now]);}while (o<=q&&s[o].r==u) {ans[s[o].id]=ans[s[o].id]+get(R[lalal[s[o].k]])-get(L[lalal[s[o].k]]-1);o++;}}
}
void solve2 ()
{memset(f,0,sizeof(f));sort(s+1,s+1+q,cmpl);int o=1;while (o<=q&&s[o].l==0) o++;for (int u=1;u<=n;u++){int len=ss[u].size(),now=0;for (int i=0;i<len;i++){int x=ss[u][i]-'a';now=tr[now].son[x];change(L[now]);}while (o<=q&&s[o].l==u){ans[s[o].id]=ans[s[o].id]-(get(R[lalal[s[o].k]])-get(L[lalal[s[o].k]]-1));o++;}}
}
void dfs (int x)
{L[x]=++num;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;dfs(y);}R[x]=num;
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&q);for (int u=1;u<=n;u++){now=0;char ch=getchar();while (ch<'a'||ch>'z') ch=getchar();while (ch>='a'&&ch<='z') {ss[u].push_back(ch);Ins(ch-'a');ch=getchar();}lalal[u]=now;}get_fail();for (int u=1;u<=tot;u++)    init(tr[u].fail,u);num=0;dfs(0);
// for (int u=1;u<=tot;u++) printf("%d %d\n",L[u],R[u]);for (int u=1;u<=q;u++)  {
   scanf("%d%d%d",&s[u].l,&s[u].r,&s[u].k);s[u].id=u;s[u].l--;}solve1();solve2();for (int u=1;u<=q;u++) printf("%lld\n",ans[u]);return 0;
}