bzoj 3881: [Coci2015]Divljak AC自动机

题目大意:

http://www.lydsy.com/JudgeOnline/problem.php?id=3881

题解:

这道题我想出了三种做法,不过只有最后一种能过。

第一种:

首先我们把所有的操作离线下来,把所有的字符串全部插入,构建fail树

对于每个字符串记录插入时间,并设S集合中的字符串的插入时间为无限大

然后对于每一个询问,查找fail树中以\(S_x\)为根的子树里有多少插入时间小于询问时间的节点。

这一步可以处理出dfs序后用可持久化线段树搞。

但是它TLE了,我觉得这种做法完全没有问题啊,为什么还是TLE了....

第二种:

首先只插入S集合中所有的字符串,然后构建AC自动机,求出fail树

然后对于每一次向T集合中的插入,我们把这个串扔到自动机里

这时候我们发现,这个串仍到AC自动机里后经过的所有的状态的对应的串都多出现了一次

所以我们知道,经过的所有的节点及其到fail树的根的路径上的点代表的串都多出现了一次

所以将所有经过的状态的节点拿出来,按照dfs序排序,将所有节点到根的路径上的节点都+1

相邻节点的lca到根的路径上的节点-1.(dfs序最大的和dfs最小的不相邻)

这个操作我们用树链剖分套线段树即可\(O(nlog^2n)\) TLE

第三种:

仔细考虑一下发现上面的操作可以用单点修改,子树查询的方式搞掉

所以在dfs序上用树状数组就好了啊....

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 2000010;

int ch[maxn][26],nodecnt;

int mp[maxn];

char s[2000010];

inline void insert(const int &pos){

    int len = strlen(s),nw = 0;

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

        int c = s[i] - 'a';

        if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;

        nw = ch[nw][c];

    }mp[pos] = nw;

}

int fail[maxn],q[maxn];

inline void build(){

    int l = 0,r = -1;

    for(int c=0;c<26;++c){

        if(ch[0][c]){

            fail[ch[0][c]] = 0;

            q[++r] = ch[0][c];

        }

    }

    while(l <= r){

        int u = q[l++];

        for(int c=0;c<26;++c){

            int t = ch[fail[u]][c];

            if(!ch[u][c]) ch[u][c] = t;

            else{

                fail[ch[u][c]] = t;

                q[++r] = ch[u][c];

            }

        }

    }

}

struct Edge{

    int to,next;

}G[maxn<<1];

int head[maxn],cnt;

void add(const int &u,const int &v){

    G[++cnt].to = v;

    G[cnt].next = head[u];

    head[u] = cnt;

}

#define v G[i].to

int fa[maxn],ind[maxn],oud[maxn],dfs_clock;

int siz[maxn],son[maxn],dep[maxn];

void dfs(const int &u){

    siz[u] = 1;

    for(int i = head[u];i;i=G[i].next){

        if(v == fa[u]) continue;

        fa[v] = u;

        dep[v] = dep[u] + 1;

        dfs(v);

        siz[u] += siz[v];

        if(siz[son[u]] < siz[v]) son[u] = v;

    }

}

int top[maxn];

void dfs(const int &u,const int &tp){

    top[u] = tp;ind[u] = ++dfs_clock;

    if(son[u]) dfs(son[u],tp);

    for(int i = head[u];i;i=G[i].next){

        if(v == son[u] || v == fa[u]) continue;

        dfs(v,v);

    }oud[u] = dfs_clock;

}

#undef v

inline int lca(int u,int v){

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

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

        u = fa[top[u]];

    }return dep[u] < dep[v] ? u : v;

}

#define lowbit(x) (x&-x)

int c[maxn+100];

inline void modify(int x,int y){

    for(;x <= dfs_clock + 10;x += lowbit(x)) c[x] += y;

}

inline int query(int x){

    int ret = 0;

    for(;x;x-=lowbit(x)) ret += c[x];

    return ret;

}

int a[maxn];

inline bool cmp(const int &i,const int &j){

    return ind[i] < ind[j];

}

inline void find(){

    int len = strlen(s),nw = 0;

    a[0] = 0;

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

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

        a[++a[0]] = nw+1;

    }sort(a+1,a+a[0]+1,cmp);

    int p = 1;

    for(int i=1;i<=a[0];++i){

        if(a[i] != a[i-1] || i == 1) a[p++] = a[i];

    }a[0] = p-1;

    for(int i=1;i<=a[0];++i){

        modify(ind[a[i]],1);

        if(i != a[0]) modify(ind[lca(a[i],a[i+1])],-1);

    }

}

int main(){

    int n;read(n);

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

        scanf("%s",s);

        insert(i);

    }build();

    for(int i=1;i<=nodecnt;++i) add(fail[i]+1,i+1);

    dfs(1);dfs(1,1);

    int m;read(m);

    int op;

    while(m--){

        read(op);

        if(op == 1){

            scanf("%s",s);

            find();

        }else{

            read(op);

            printf("%d\n",query(oud[mp[op]+1]) - query(ind[mp[op]+1]-1));

        }

    }

    getchar();getchar();

    return 0;

}

巴特西

bzoj 3881: [Coci2015]Divljak AC自动机

题目大意:

题解:

最新文章

热门文章