[Coci2015]Divljak

题目描述

Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。

接下来会发生q个操作，操作有两种形式：

“1 P”，Bob往自己的集合里添加了一个字符串P。

“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的子串）

Bob遇到了困难，需要你的帮助。

题解

多串匹配问题，可以想到用AC自动机维护。

对于这种询问，每个串至多贡献一次的问题。

先是把每个T串在AC自动机上跑一遍，获得了一个点集，那么这些点在fail树上到根的路径上的所有点都会被贡献一次。

相当于这些链的并都被贡献了。

那我们的任务就是求链并。

一种方法是将所有点排一个序，然后对每个点到根的路径上加1，相邻两个点的LCA处-1。

链加不太好写，可以转化成统计子树和的形式，用BIT维护。

代码

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define N 2000002

using namespace std;

typedef long long ll;

queue<int>q;

int tot,ch[N][],head[N],f[N],zh[N],topp,n,tr[N],tag[N],size[N],deep[N],fa[N],son[N],top[N],dfn[N],dfnn,tott,fan[N];

char s[N];

inline ll rd(){

    ll x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

struct edge{int n,to;}e[N];

inline void add(int u,int v){

e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}

inline void get_fail(){

    for(int i=;i<;++i)if(ch[][i]){q.push(ch[][i]),add(,ch[][i]);}

    while(!q.empty()){

        int u=q.front();q.pop();

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

            if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],add(f[ch[u][i]],ch[u][i]),q.push(ch[u][i]);

            else ch[u][i]=ch[f[u]][i];

        }

    }

}

inline void upd(int x,int y){while(x<=dfnn)tr[x]+=y,x+=x&-x;}

inline int query(int x){int ans=;while(x)ans+=tr[x],x-=x&-x;return ans;}

inline void ins(int id){

    int len=strlen(s);int now=;

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

        if(!ch[now][s[i]-'a'])ch[now][s[i]-'a']=++tott;

        now=ch[now][s[i]-'a'];

    }

    tag[id]=now;

}

void dfs(int u){

    size[u]=;//cout<<u<<" ";

    for(int i=head[u];i;i=e[i].n){

        int v=e[i].to;deep[v]=deep[u]+;fa[v]=u;

        dfs(v);

        size[u]+=size[v];

        if(size[v]>size[son[u]]||!son[u])son[u]=v;

    }

}

void dfs2(int u){

    if(!top[u])top[u]=u;dfn[u]=++dfnn;fan[dfnn]=u;

    if(son[u])top[son[u]]=top[u],dfs2(son[u]);

    for(int i=head[u];i;i=e[i].n){

        int v=e[i].to;

        if(v!=son[u])dfs2(v);

    }

}

int getlca(int u,int v){

    while(top[u]!=top[v]){

        if(deep[top[u]]<deep[top[v]])swap(u,v);

        u=fa[top[u]];

    }

    return min(dfn[u],dfn[v]);

}

int main(){

    n=rd();

    for(int i=;i<=n;++i){scanf("%s",s);ins(i);}

    get_fail();

    dfs();dfs2();

    int q=rd();

    while(q--){

        int opt=rd();

        if(opt==){

            scanf("%s",s);int len=strlen(s),now=;topp=;

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

                now=ch[now][s[i]-'a'];

                zh[++topp]=dfn[now];

            }

            sort(zh+,zh+topp+);

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

                upd(zh[i],);

                if(i!=)upd(getlca(fan[zh[i-]],fan[zh[i]]),-);

            }

        }

        else{

            int x=tag[rd()];

            printf("%d\n",query(dfn[x]+size[x]-)-query(dfn[x]-));

        }

    }

    return ;

}

巴特西

[Coci2015]Divljak

最新文章

热门文章