「Bzoj 2434」「Noi2011」阿狸的打字机 (AC自动机Fail树+DFS序+树状数组)

发表于 | 分类于 | | + s

Bzoj 2434
题意：见上。

先介绍 Trie，Trie图，Fail树

将字符串插入 Trie 即可得到下图
Markdown

将失配函数连上，得到Trie图
Markdown

Trie图可以将字符串问题转化为图论问题，具体可以看Bzoj 2938

将原边删掉，失配边反向，得到Fail树
Markdown

Fail树每个点的祖先节点都是这个点失配后可以走到的点。
对于AC自动机中的每一个节点，如果节点A的失配边指向节点B，就会发现B对应的字符串一定在A对应的字符串中出现，那么在Fail树上显然可以利用这一性质。

考虑暴力，即在Fail树上往上跳。

我们还可以离线，将$y$相等的并成一块，一起处理，能过$70$分。

逆向思维，我们考虑对于每个$x$去找$y$，那么标记一下$y$能跳到的点，求子树和即可。显然可以树状数组维护DFS序。

而这样还是不能通过。我们发现每次初始化$y$能跳到的点进树状数组时，时间开销非常大。我们考虑边加边统计。

我们在原Trie树上DFS，将当前点$u$根路径上的点标记为$1$，然后再Fail树上求每个$u$对应的询问的$x$的子树和即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    // AC自动机 
    int Q, ch[MAXN][26], fa[MAXN], f[MAXN], val[MAXN], sz, pos[MAXN];
    char s[MAXN];

    queue<int > q;
    void getFail() {
        for (int c = 0; c < 26; ++c) {
            int v = ch[0][c];
            if (v) q.push(v), f[v] = 0;
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < 26; ++c) {
                int v = ch[u][c];
                if (!v) continue ;
                q.push(v);
                int j = f[u];
                while (j && !ch[j][c]) j = f[j];
                f[v] = ch[j][c];
            }
        }
    }

    // Fail树 
    vector<int > G[MAXN];
    int dfn[MAXN], rr[MAXN], idx;

    void ins(int u, int v) {G[u].push_back(v);}

    void dfs_pre(int u, int p) {
        dfn[u] = ++idx;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != p) dfs_pre(v, u);
        }
        rr[u] = idx;
    }

    // 树状数组
    int c[MAXN]; 
    int lowbit(int x) {return x & (-x);}
    void add(int x, int v) {for (int i = x; i <= sz + 1; i += lowbit(i)) c[i] += v;}
    int query(int x) {int ret = 0; for (int i = x; i > 0; i -= lowbit(i)) ret += c[i]; return ret;}

    // 询问
    struct qry {
        int x, y, id;
        bool operator < (const qry &rhs) const {return y < rhs.y;}
    } xw[MAXN]; 
    int ql[MAXN], qr[MAXN], ans[MAXN];

    void dfs_ans(int u, int p) {
        add(dfn[u], 1);
        if (val[u]) for (int i = ql[u]; i <= qr[u]; ++i) 
            ans[xw[i].id] = query(rr[pos[xw[i].x]]) - query(dfn[pos[xw[i].x]] - 1);
        for (int c = 0; c < 26; ++c) {
            int v = ch[u][c];
            if (v) dfs_ans(v, u);
        }
        add(dfn[u], -1);
    }

    void clean() {
        ms(ch, 0), ms(fa, 0), ms(f, 0), ms(val, 0), sz = 0;
        ms(dfn, 0), ms(rr, 0), idx = 0;
        ms(c, 0);
    }
    int solve() {

        clean(); 
        scanf("%s", s);

        int len = strlen(s), now = 0, cnt = 0;
        for (int i = 0; i < len; ++i) {
            if (s[i] == 'P')
                val[now] = 1, pos[++cnt] = now;
            else if (s[i] == 'B')
                now = fa[now];
            else {
                int c = s[i] - 'a';
                if (!ch[now][c]) ch[now][c] = ++sz;
                fa[ch[now][c]] = now, now = ch[now][c];
            }
        }

        getFail();
        for (int i = 1; i <= sz; ++i) ins(i, f[i]), ins(f[i], i);
        dfs_pre(0, -1);

        cin >> Q;
        for (int i = 1; i <= Q; ++i) scanf("%d%d", &xw[i].x, &xw[i].y), xw[i].id = i;
        sort(xw + 1, xw + 1 + Q);

        for (int p = 1, i = 1; i <= Q; i = p) {
            ql[pos[xw[i].y]] = qr[pos[xw[i].y]] = i;
            while (xw[i].y == xw[++p].y) ++qr[pos[xw[i].y]];
        }
        dfs_ans(0, -1);

        for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
abbPcP
1
1 2

abbPcP
1
1 1
*/
------ 本文结束 ------