CodeForces 547E：Mike and Friends（AC自动机+DFS序+主席树）

What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of n bears (including Mike) numbered from 1 to n.

Phone number of i-th member of CF is s_i. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as call(i, j) the number of times that i-th member of CF called the j-th member of CF.

The geek Mike has q questions that he wants to ask you. In each question he gives you numbers l, r and k and you should tell him the number

Input

The first line of input contains integers n and q (1 ≤ n ≤ 2 × 10⁵ and 1 ≤ q ≤ 5 × 10⁵).

The next n lines contain the phone numbers, i-th line contains a string s_iconsisting of lowercase English letters ().

The next q lines contain the information about the questions, each of them contains integers l, r and k (1 ≤ l ≤ r ≤ n and 1 ≤ k ≤ n).

Output

Print the answer for each question in a separate line.

Examples

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

题意：给定N个串，M次询问，每次询问[L,R]里含多少个X。

思路：（第一次做，结合主席树那里还是不太好想）。对N个串建立AC自动机，建立Fail树，然后得到DFS序。那么，对于每个串S，假设其长度为L，S在AC自动机上面跑，其每个前缀Si在AC自动机上面得到最大深度，对应的Fail树位置，贡献加1，保证这个贡献在Si的后缀的子树里（比如abcdef，那么跑到abcd时，在fail树上面对应的位置贡献加1 ，对于后缀abcd,bcd,cd,d的子树都含这个贡献）。

关键是如何出现子树来自于[L,R]的贡献。开始我以为以dfs序为X轴，以来自的串为Y轴建立主席树，查询的时候查询区间[in[u],out[u]]，即子树里关键字在[L,R]里的个数。但是发现没有转移关系。所以想不走了。

看了其他人的代码，是以每个串，以来自的串为X轴（从长的前缀到短的前缀），以dfs序为X轴，保证了前缀和的正确性，查询的时候查询区间[L-1,R]的区间在[in[[u],out[u]]的数量。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int ch[maxn][],fa[maxn],cnt=; //trie树

int Laxt[maxn],Next[maxn],To[maxn],tot; //fail树

int q[maxn],fail[maxn],head,tail; //fail树

int in[maxn],out[maxn],pos[maxn],times;//dfs序

int p[maxn],rt[maxn],cur,num; struct in{int l,r,sum;}s[maxn*];

char c[maxn];

void addedge(int u,int v){ Next[++tot]=Laxt[u]; Laxt[u]=tot; To[tot]=v; }

int insert()

{

    int Now=; for(int i=;c[i];i++){

        if(!ch[Now][c[i]-'a']){

             ch[Now][c[i]-'a']=++cnt;

             fa[cnt]=Now;

        }

        Now=ch[Now][c[i]-'a'];

    }   return Now;

}

void buildfail()

{

    for(int i=;i<;i++){

        if(ch[][i]) q[++head]=ch[][i],fail[ch[][i]]=;

        else ch[][i]=;

    }

    while(tail<head){

        int Now=q[++tail];

        for(int i=;i<;i++){

            if(ch[Now][i]) {

                q[++head]=ch[Now][i]; fail[ch[Now][i]]=ch[fail[Now]][i];

            }

            else ch[Now][i]=ch[fail[Now]][i];

        }

    }

    for(int i=;i<=cnt;i++) addedge(fail[i],i);

}

void dfs(int u)

{

    in[u]=++times;

    for(int i=Laxt[u];i;i=Next[i]) dfs(To[i]);

    out[u]=times;

}

void add(int &Now,int pre,int L,int R,int pos)

{

    Now=++num; s[Now]=s[pre]; s[Now].sum++;

    if(L==R) return ; int Mid=(L+R)>>;

    if(pos<=Mid) add(s[Now].l,s[pre].l,L,Mid,pos);

    else add(s[Now].r,s[pre].r,Mid+,R,pos);

}

int query(int pre,int Now,int L,int R,int l,int r)

{

    if(l<=L&&r>=R) return s[Now].sum-s[pre].sum;

    int res=,Mid=(L+R)>>;

    if(l<=Mid) res+=query(s[pre].l,s[Now].l,L,Mid,l,r);

    if(r>Mid) res+=query(s[pre].r,s[Now].r,Mid+,R,l,r);

    return res;

}

int main()

{

    int N,M,Q,L,R,x,i,j;

    scanf("%d%d",&N,&Q);

    for(i=;i<=N;i++){

        scanf("%s",c+);

        pos[i]=insert();

    }

    buildfail();

    dfs(); cur=;

    for(i=;i<=N;i++){

        for(j=pos[i];j;j=fa[j]){

            cur++;

            add(rt[cur],rt[cur-],,times,in[j]);

        }

        p[i]=rt[cur];

    }

    while(Q--){

        scanf("%d%d%d",&L,&R,&x);

        printf("%d\n",query(p[L-],p[R],,times,in[pos[x]],out[pos[x]]));

    }

    return ;

}

巴特西

CodeForces 547E：Mike and Friends（AC自动机+DFS序+主席树）

最新文章

热门文章