DDOSvoid's Blog

CF 547E Mike and Friends

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

题目描述

https://codeforces.com/problemset/problem/547/E

简要题意：给定 $n$ 个字符串 $S_i$，$m$ 次询问 $S_k$ 在 $S_l,S_{l+1},\cdots,S_r$ 中出现的次数和

$n,\sum|S|\le 2\times 10^5,m\le 5\times 10^5$

Solution

注意到 $S_k$ 的出现次数和是 $S_k$ 的结束节点的子树内的有贡献的串的前缀节点的个数和

我们考虑离线同时将询问差分，相当于每次加入一个串的所有前缀节点，然后查询区间和，可以使用树状数组实现

时间复杂度 $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
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define maxn 200010
#define maxm 500010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

#define ch s[i] - 'a'
struct AC_automaton {
    int nxt[26], fail;
} T[maxn]; int top = 1, rt = 1, bl[maxn];
void insert(char *s, int k) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } bl[k] = now;
} 

void init_fail() { // Trie 图
    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); 
    }
    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);
        }
    }
}

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];
void dfs(int u) {
    static int cnt = 0;
    in[u] = ++cnt;
    for (int i = head[u]; ~i; i = e[i].next) dfs(e[i].to);
    out[u] = cnt;
}

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 n, m, pos[maxn];
char s[maxn];

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

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s + pos[i]; insert(s + pos[i], i); 
        pos[i + 1] = pos[i] + strlen(s + pos[i]);
    } init_fail();
    for (int i = 1; i <= top; ++i) add_edge(T[i].fail, i);
    dfs(rt);
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        A[y].emplace_back(z, i);
        B[x - 1].emplace_back(z, i); 
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = pos[i], now = rt; j < pos[i + 1]; ++j) {
            now = T[now].nxt[s[j] - 'a'];
            add(in[now], 1); 
        }
        for (auto [t, id] : A[i]) ans[id] += get_sum(out[bl[t]]) - get_sum(in[bl[t]] - 1);
        for (auto [t, id] : B[i]) ans[id] -= get_sum(out[bl[t]]) - get_sum(in[bl[t]] - 1); 
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0; 
}