本文共 1883 字，大约阅读时间需要 6 分钟。

题意

有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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;const int N=500005;int n,q;vector
         
           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
          
            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
           
            =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
            
             '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;}