我的blog

题目链接：洛谷P5840 [COCI2015]Divljak

\(vijos\)上我的个人域题题目链接：Divljak

\[preface\]

本文版权归博客园，洛谷博客和蒟蒻wjr所有，欢迎转载，但需保留此段声明，并给出原文链接，如有侵权行为，还请不吝啬向博主举报，谢谢合作。

一道AC自动机+LCA+树链剖分+树上差分+树状数组维护的恶心题

\[description\]

首先理解trie，树上任意一个节点到跟节点是插入串的前缀，而\(nxt\)指针是指向这个前缀的后缀。

我们建一棵关于这样的树，一个节点的子树上的所有节点到根都是把其这个节点当做后缀，那我们就建一棵树。

先将\(S\)串集合建一个AC自动机

然后将\((nxt[u],u)\)插入这条树(是另建一棵树，不是AC自动机的Trie树)的边，显然如果\(nxt[u]=0\)连向的是根节点
(我的代码根节点是\(0\)，所以不做判断)。

接着再将建好的那棵树求出每个节点的\(dfs\)序。

我们用到树上差分的思想，然后把要插入的\(T\)集合在\(Trie\)树中统计走过的节点，记录下来，再按\(dfn\)排序，将相邻两个节点的在树上的位置\(+1\)，表示多一个串匹配，但是他们的\(LCA\)和\(LCA\)的祖先很明显是\(+2\)串匹配，不符合我们此串在\(T\)集合中的出现次数，所以将两个节点的\(LCA\)的位置标记\(-1\)。

对于此过程，我们可以用树状数组统计答案，将此树树链剖分后，按每个节点的dfs序维护，同时也可以跑\(LCA\)，则\(S\)串在\(T\)集合中的出现次数为其节点和其子树的之和。

\[code\]

#include <cstdio>
#include <queue>
#include <cassert>
#include <algorithm>
#define re register
using namespace std;
const int N=2e6+5,M=1e5+5;
int ch[N][26],nxt[N],tot;
int pos[M];
inline void insert(char *s,int id)
{
    int u=0;
    for(re int i=0; s[i]; ++i)
    {
        int c=s[i]-'a';
        if(!ch[u][c])
            ch[u][c]=++tot;
        u=ch[u][c];
    }
    pos[id]=u;
}
struct Edge
{
    int next,to;
} edge[N];
int head[N],num_edge;
inline void add_edge(int from,int to)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    head[from]=num_edge;
}
inline void build()
{
    queue<int>q;
    for(re int i=0; i<26; ++i)
        if(ch[0][i])
            q.push(ch[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(re int i=0; i<26; ++i)
            if(!ch[u][i])
                ch[u][i]=ch[nxt[u]][i];
            else
            {
                q.push(ch[u][i]);
                nxt[ch[u][i]]=ch[nxt[u]][i];
            }
    }
}
int fa[N],top[N],dep[N],size[N],son[N];
inline void dfs1(int u,int fa_)
{
    fa[u]=fa_;
    size[u]=1;
    dep[u]=dep[fa_]+1;
    for(re int i=head[u]; i; i=edge[i].next)
    {
        int &v=edge[i].to;
        dfs1(v,u);
        size[u]+=size[v];
        if(!son[u]||size[v]>size[son[u]])
            son[u]=v;
    }
}
int dfn[N],dfstime;
inline void dfs2(int u,int topf)
{
    top[u]=topf;
    dfn[u]=++dfstime;
//  printf("%d ",u);
    if(!son[u])return;
    dfs2(son[u],topf);
    for(re int i=head[u]; i; i=edge[i].next)
    {
        int &v=edge[i].to;
        if(v==son[u])
            continue;
        dfs2(v,v);
    }
}
inline int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    return x;
}
int n,q;
char str[N];
int a[N];
int lowbitsum[N];
#define lowbit(x) (x&(-x))
inline void update(int x,int y)
{
//  assert(x>=1);
    for(; x<=dfstime; x+=lowbit(x))
        lowbitsum[x]+=y;
}
inline int query(int x)
{
//  assert(x>=1);
    int res=0;
    for(; x; x-=lowbit(x))
        res+=lowbitsum[x];
    return res;
}
inline bool cmp(const int &x,const int &y)
{
    return dfn[x]<dfn[y];
}
inline void solve1()
{
    int u=0,tp=0;
    for(re int i=0; str[i]; ++i)
    {
        u=ch[u][str[i]-'a'];
        a[++tp]=u;
    }
//  for(re int i=1; i<=tp; ++i)
//      printf("%d ",a[i]);
    sort(a+1,a+1+tp,cmp);
    bool flag=false;
    for(re int i=1; i<=tp; ++i)
    {
        update(dfn[a[i]],1);
        if(flag)
            update(dfn[LCA(a[i],a[i-1])],-1);
        else
            flag=true;
    }
}
inline void solve2()
{
    int x;
    scanf("%d",&x);
    printf("%d\n",query(dfn[pos[x]]+size[pos[x]]-1)-query(dfn[pos[x]]-1));
}
int main()
{
    scanf("%d",&n);
    for(re int i=1; i<=n; ++i)
    {
        scanf("%s",str);
        insert(str,i);
    }
    build();
//  for(re int i=1; i<=tot; ++i)
//      printf("%d %d\n",nxt[i],i);
    for(re int i=1; i<=tot; ++i)
        add_edge(nxt[i],i);
//  printf("%d\n",num_edge);
    dfs1(0,tot+1);
    dfs2(0,0);
//  printf("%d\n",dfstime);
//  for(re int i=0; i<=tot; ++i)
//      printf("%d ",dfn[i]);
    scanf("%d",&q);
    while(q--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%s",str);
            solve1();
        }
        else if(opt==2)
            solve2();
    }
    return 0;
}