题解 SP8093 【JZPGYZ - Sevenk Love Oimaster】

· · 题解

感谢给我提供区间数颜色这个思路的i207M神犇qwq……

很显然我们要对所有模板串建一个广义后缀自动机，然后对每个询问串在上面运行看能跑到哪个点（如果是空节点就不是任何串的子串了），那么现在我们的问题就变成了求后缀自动机上的点表示的字符串都在哪些串内出现过。

由于Parent树上子节点出现过的地方其祖先也一定出现过，所以我们在建SAM的时候不妨对新建的节点标记一下他属于当前字符串，那么问题就转化为了这个点的Parent子树里有多少种不同的标记，我们把这个树转换为dfs序列，就变成了经典的区间数颜色问题。

这个区间数颜色并没有修改，因此我们可以离线做，就是扫一遍dfs序列，然后把询问存在右端点上，维护每个颜色最后的出现位置，用树状数组维护这个地方作为最后出现位置有多少个颜色，于是就能做了。

上代码~

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
namespace ywy
{
    char str[400001];
    int sam[800001][26],fa[800001],len[800001];
    inline int get()
    {
        char c;
        register int ptr=1;
        while((c=getchar())||23333)if(c>='a'&&c<='z')break;
        str[ptr]=c;
        ptr++;
        while((c=getchar())||23333)
        {
            if(c>='a'&&c<='z')str[ptr]=c,ptr++;
            else return(ptr-1);
        }
    } int c[800001],heads[800001],fheads[800001],dfn[800001],size[800001];
    typedef struct _b
    {
        int dest;
        int nxt;
    } bian;
    bian memchi[800001];
    int gnn=1;
    inline void add(int s,int t)
    {
        memchi[gnn].dest=t;
        memchi[gnn].nxt=heads[s];
        heads[s]=gnn;
        gnn++;
    } int col[800001],idfn[800001];
    typedef struct _q
    {
        int l;
        int nxt;
    } query;
    query nodes[60001];
    int gdfn=1;
    void dfs(int pt)
    {
        size[pt]=1;
        dfn[pt]=gdfn;
        idfn[gdfn]=pt;
        gdfn++;
        for(register int i=heads[pt]; i; i=memchi[i].nxt)
        {
            dfs(memchi[i].dest);
            size[pt]+=size[memchi[i].dest];
        }
    } int anss[60001];
    void print(int num)
    {
        if(num>=10)print(num/10);
        putchar(num%10+'0');
    } int gn=2;
    inline int zhuanyi(int p,int x,int cjr)
    {
        int me=gn;
        gn++;
        len[me]=len[p]+1;
        col[me]=cjr;
        while(p&&!sam[p][x])sam[p][x]=me,p=fa[p];
        if(!p)
        {
            fa[me]=1;
            return(me);
        }
        int q=sam[p][x];
        if(len[q]==len[p]+1)
        {
            fa[me]=q;
            return(me);
        }
        int nq=gn;
        gn++;
        len[nq]=len[p]+1;
        for(register int i=0; i<26; i++)sam[nq][i]=sam[q][i];
        fa[nq]=fa[q];
        fa[q]=fa[me]=nq;
        while(p&&sam[p][x]==q)sam[p][x]=nq,p=fa[p];
        return(me);
    } int pos[10001];
    void ywymain()
    {
        int N,q;
        cin>>N>>q;
        int p;
        for(register int cjr=1; cjr<=N; cjr++)
        {
            p=1;
            int n=get();
            for(register int i=1; i<=n; i++)p=zhuanyi(p,str[i]-'a',cjr);
        }
        for(register int i=2; i<gn; i++)add(fa[i],i);
        dfs(1);
        for(register int cjr=1; cjr<=q; cjr++)
        {
            int cur=1;
            int n=get();
            for(register int i=1; i<=n; i++)cur=sam[cur][str[i]-'a'];
            if(!cur)continue;
            nodes[cjr].l=dfn[cur];
            nodes[cjr].nxt=fheads[dfn[cur]+size[cur]-1];
            fheads[dfn[cur]+size[cur]-1]=cjr;
        }
        for(register int i=1; i<gn; i++)
        {
            if(col[idfn[i]])
            {
                if(pos[col[idfn[i]]])
                {
                    for(register int j=pos[col[idfn[i]]]; j<=gn; j+=(j&-j))c[j]--;
                }
                for(register int j=i; j<=gn; j+=(j&-j))c[j]++;
                pos[col[idfn[i]]]=i;
            }
            for(register int j=fheads[i]; j; j=nodes[j].nxt)
            {
                int tot=0;
                for(register int k=nodes[j].l-1; k>0; k-=(k&-k))tot-=c[k];
                for(register int k=i; k>0; k-=(k&-k))tot+=c[k];
                anss[j]=tot;
            }
        }
        for(register int i=1; i<=q; i++)print(anss[i]),putchar('\n');
    }
}
int main()
{
    ywy::ywymain();
    return(0);
}