【BZOJ-3881】Divljak AC自动机fail树 + 树链剖分+ 树状数组 + DFS序

时间：2023-03-08 21:09:01

3881: [Coci2015]Divljak

Time Limit: 20 Sec  Memory Limit: 768 MB
Submit: 508  Solved: 158
[Submit][Status][Discuss]

Description

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遇到了困难，需要你的帮助。

Input

第1行，一个数n；
接下来n行，每行一个字符串表示S_i；
下一行，一个数q；
接下来q行，每行一个操作，格式见题目描述。

Output

对于每一个Alice的询问，帮Bob输出答案。

Sample Input

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3

Sample Output

1
2
1

HINT

【数据范围】
1 <= n,q <= 100000；
Alice和Bob拥有的字符串长度之和各自都不会超过 2000000；
字符串都由小写英文字母组成。

Source

鸣谢 Dzy

Solution

首先这个题得利用fail树的性质....

这种给出一个串在给出的一坨串中出现次数或者是否出现过，这样显然是利用fail树...

然后就是把路径上的点变成1，询问有多少个1...这个可以利用树状数组维护DFS序得到...

然后这个题就是先把Alice的串建AC自动机并且建出fail树...

然后每得到Bob的串，就在fail树上相应的点上+1，但是直接+1会有重复，所以先对所有的点排序，然后直接将+1标记打在节点上，并对相邻节点的LCA上打上-1标记，这样询问就转化成求子树和。

数据规模比较大，倍增LCA会被卡..

其实正解应该建虚树...这样的复杂度还是比较玄学....建虚树应该是比较保险的方法.

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

inline int read()

{

    int x=; char ch=getchar();

    while (ch<'' || ch>'') ch=getchar();

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x;

}

#define MAXN 2000100

int N,Q,id[MAXN];

char S[MAXN];

namespace ACMachine

{

    struct TrieNode{int son[MAXN][],fail[MAXN],end[MAXN];}trie;

    int sz=;

    inline void Insert(int x)

    {

        int now=,len=strlen(S+);

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

            if (trie.son[now][S[i]-'a']) now=trie.son[now][S[i]-'a'];

                else now=trie.son[now][S[i]-'a']=++sz,now=sz;

        trie.end[now]=;

        id[x]=now;

    }

    inline void Buildfail()

    {

        queue<int>q; q.push();

        while (!q.empty())

            {

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

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

                    if (trie.son[now][i])

                        {

                            int fa=trie.fail[now];

                            while (fa && !trie.son[fa][i]) fa=trie.fail[fa];

                            trie.fail[trie.son[now][i]]=fa? trie.son[fa][i] : ;

                            q.push(trie.son[now][i]);

                        }

            }

    }

}

using namespace ACMachine;

namespace FailTree

{

    struct EdgeNode{int next,to;}edge[MAXN<<];

    int head[MAXN],cnt;

    inline void AddEdge(int u,int v) {cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}

    inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}

    inline void BuildTree() {for (int i=; i<=sz; i++) InsertEdge(trie.fail[i],i);}

}

using namespace FailTree;

namespace Divide

{

    int size[MAXN],deep[MAXN],fa[MAXN],son[MAXN],pl[MAXN],dfn,pre[MAXN],top[MAXN],pr[MAXN];

    inline void DFS_1(int now,int last)

    {

        size[now]=;

        for (int i=head[now]; i; i=edge[i].next)

            if (edge[i].to!=last)

                {

                    deep[edge[i].to]=deep[now]+;

                    fa[edge[i].to]=now;

                    DFS_1(edge[i].to,now);

                    size[now]+=size[edge[i].to];

                    if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;

                }

    }

    inline void DFS_2(int now,int chain)

    {

        pl[now]=++dfn; pre[dfn]=now; top[now]=chain;

        if (son[now]) DFS_2(son[now],chain);

        for (int i=head[now]; i; i=edge[i].next)

            if (edge[i].to!=fa[now] && edge[i].to!=son[now])

                DFS_2(edge[i].to,edge[i].to);

        pr[now]=dfn;

    }

    inline int LCA(int x,int y)

    {

        while (top[x]!=top[y])

            {

                if (deep[top[x]]<deep[top[y]]) swap(x,y);

                x=fa[top[x]];

            }

        return deep[x]<deep[y]? x:y;

    }

}

using namespace Divide;

namespace BIT

{

    int tree[MAXN];

    inline int lowbit(int x) {return x&-x;}

    inline void Modify(int p,int d) {for(int i=p; i<=sz; i+=lowbit(i)) tree[i]+=d;}

    inline int Query(int p) {int re=; for (int i=p; i; i-=lowbit(i)) re+=tree[i]; return re;}

    inline int Query(int l,int r) {return Query(r)-Query(l-);}

}

using namespace BIT;

int st[MAXN],tp,to;

inline bool cmp(int x,int y) {return pl[x]<pl[y];}

int main()

{

    N=read();

    for (int i=; i<=N; i++) scanf("%s",S+),ACMachine::Insert(i);

    ACMachine::Buildfail();

    FailTree::BuildTree();

    DFS_1(,); DFS_2(,);

    Q=read();

    while (Q--)

        {

            int opt=read(),le; char str[MAXN];

            switch (opt)

                {

                    case :

                        scanf("%s",str+); le=strlen(str+); tp=to=;

                        for (int now=,i=; i<=le; i++)

                            {

                                while (now && !trie.son[now][str[i]-'a']) now=trie.fail[now];

                                now=trie.son[now][str[i]-'a'];

                                if (now!=) st[++tp]=now;

                            }

                        sort(st+,st+tp+,cmp);

                        st[to]=-; for (int i=; i<=tp; i++) if (st[to]!=st[i]) st[++to]=st[i];

                        for (int i=; i<=to; i++) Modify(pl[st[i]],);

                        for (int i=; i<=to; i++) Modify(pl[LCA(st[i-],st[i])],-);

                    break;

                    case : int x=read(); printf("%d\n",Query( pl[id[x]] , pr[id[x]] )); break;

                }

        }

    return ;

}

想找个机会整理一下fail树的一些性质....

相关文章