DDOSvoid's Blog

Luogu P2414 [NOI2011] 阿狸的打字机

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P2414

简要题意：给定一棵 $Trie$ 以及 $m$ 次询问，每次询问给出 $x,y$，求第 $x$ 个串在第 $y$​ 个串中出现多少次

$len\le 10^5,m\le 10^5$

Solution

我们要求的就是 $fail$ 树上 $x$ 的子树内有多少点是 $y$ 的前缀节点

我们将询问离线下来挂到 $y$ 上，在遍历的 $Trie$ 的过程中维护当前所在点的所有前缀节点，我们只需要将其加入到树状数组中即可，查询就是就相当于一个区间查询

时间复杂度 $O(L\log L)$​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <tuple>
#define maxn 100010
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m;

char s[maxn];

struct Edge {
    int to, next;
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int in[maxn], out[maxn], c2; 
void dfs(int u) {
    in[u] = ++c2;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
    } out[u] = c2; 
} 

#define ch s[i] - 'a'
struct Trie {
    int nxt[26], fail;
} T[maxn]; int rt = 1, top = 1, f[maxn];
void init_fail() {
    queue<int> Q;
    for (int i = 0; i < 26; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; } 
        T[u].fail = rt; Q.push(u); add_edge(rt, u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = 0; i < 26; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
            add_edge(T[v].fail, v); 
        }
    }
} 

vector<int> A[maxn]; int bl[maxn]; 
vector<pair<int, int>> B[maxn];

int Bit[maxn];
void add(int i, int v) { while (i <= top) Bit[i] += v, i += lowbit(i); }

int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
}

int ans[maxn]; 
int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1 >> m; int l = strlen(s + 1);
    for (int i = 1, now = rt; i <= l; ++i) {
        if (s[i] == 'B') now = f[now];
        else if (s[i] == 'P') A[now].push_back(++n), bl[n] = now;
        else {
            if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
            f[T[now].nxt[ch]] = now; now = T[now].nxt[ch]; 
        } 
    }
    init_fail(); dfs(rt); 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        B[y].emplace_back(bl[x], i); 
    } 
    for (int i = 1, now = rt; i <= l; ++i) {
        if (s[i] == 'B') add(in[now], -1), now = f[now];
        else if (s[i] == 'P') 
            for (auto u : A[now])
                for (auto v : B[u]) {
                    int t, id; tie(t, id) = v;
                    ans[id] = get_sum(out[t]) - get_sum(in[t] - 1); 
                } 
        else {
            now = T[now].nxt[ch];
            add(in[now], 1); 
        }
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0;
}