Mike and Friends(AC自动机+Fail树+DFS序+可持久化线段树)

描述

传送门:Codeforces Round #305 (Div. 1) - Problem E

What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of $n$ bears (including Mike) numbered from $1$ to $n$.

Phone number of $i$-th member of CF is $s_i$. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as $call(i, j)$ the number of times that $i$-th member of CF called the $j$-th member of CF.

The geek Mike has $q$ questions that he wants to ask you. In each question he gives you numbers $l$, $r$ and $k$ and you should tell him the number $$\sum_{i = l} ^ r call(i, k)$$

Input

The first line of input contains integers $n$ and $q$ ($1 ≤ n ≤ 2 × 10^5$ and $1 ≤ q ≤ 5 × 10^5$).

The next $n$ lines contain the phone numbers, $i$-th line contains a string $s_i$ consisting of lowercase English letters ($1 ≤ \sum_\limits{i = 1} ^ n |s_i| ≤ 2 × 10^5$).

The next $q$ lines contain the information about the questions, each of them contains integers $l$, $r$ and $k$ ($1 ≤ l ≤ r ≤ n$ and $1 ≤ k ≤ n$).

Output

Print the answer for each question in a separate line.

Example

Input Output
1
2
3
4
5
6
7
8
9
10
11
5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5
1
2
3
4
5
7
5
6
3
6

思路

  • 先不考虑$[l, r]$的限制,即考虑字符串$s_k$在一个字符集合中的出现次数。
  • 只需要对字符集合建立AC自动机,$val$维护前缀的出现次数。
  • 因为fail树中$s_k$是其子节点的后缀,所以再加上子树节点的$val$值。
  • 这样就把问题转化为了求子树节点的权值之和。
  • 于是我们只需要以fail树的DFS序建线段树维护区间和即可。
  • 接下来考虑$[l, r]$的限制。这个很简单,把线段树给可持久化一下就好了。
  • 当然解决这个二维查询还有其它姿势,可以按结点深度离线用树状数组查询(口胡一下,实现也不难)。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;

#pragma optimize("-O3")

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

const int N = 1 << 18;
struct Trie
{
int ch[N][26], f[N], fa[N];
vector<int> pos;
int sz, rt;
int newnode(int u = -1)
{
fa[sz] = u;
memset(ch[sz], -1, sizeof(ch[sz]));
return sz++;
}
void init() { pos.resize(1), sz = 0, rt = newnode(); }
inline int idx(char c) { return c - 'a'; };
void insert(const string& s)
{
int u = rt;
for (auto& t : s)
{
int c = idx(t);
if (ch[u][c] == -1) ch[u][c] = newnode(u);
u = ch[u][c];
}
pos.push_back(u);
}
void build(int n)
{
queue<int> q;
f[rt] = rt;
for (int c = 0; c < 26; c++)
{
if (~ch[rt][c])
f[ch[rt][c]] = rt, q.push(ch[rt][c]);
else
ch[rt][c] = rt;
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int c = 0; c < 26; c++)
{
if (~ch[u][c])
f[ch[u][c]] = ch[f[u]][c], q.push(ch[u][c]);
else
ch[u][c] = ch[f[u]][c];
}
}
dfs_clock = 0;
for (int i = 1; i < sz; i++) G[f[i]].push_back(i);
dfs(rt);
for (int i = 1; i <= n; i++)
{
root[i] = root[i - 1];
for (int j = pos[i]; j != rt; j = fa[j])
update(in[j], 1, dfs_clock, root[i], root[i]);
}
}
vector<int> G[N];
int in[N], out[N], dfs_clock;
void dfs(int u)
{
in[u] = ++dfs_clock;
for (auto& v : G[u]) dfs(v);
out[u] = dfs_clock;
}
int root[N];
// segmemt tree
int sum[N << 5], lson[N << 5], rson[N << 5];
int tot = 0;
void update(int p, int l, int r, int& x, int y)
{
x = ++tot, lson[x] = lson[y], rson[x] = rson[y];
sum[x] = sum[y] + 1;
if (l == r) return;
int m = l + r >> 1;
if (p <= m)
update(p, l, m, lson[x], lson[y]);
else
update(p, m + 1, r, rson[x], rson[y]);
}
int query(int L, int R, int l, int r, int x, int y)
{
if (L <= l && r <= R) return sum[y] - sum[x];
int ans = 0;
int m = l + r >> 1;
if (L <= m) ans += query(L, R, l, m, lson[x], lson[y]);
if (m < R) ans += query(L, R, m + 1, r, rson[x], rson[y]);
return ans;
}
int ask(int l, int r, int k) { return query(in[pos[k]], out[pos[k]], 1, dfs_clock, root[l - 1], root[r]); }
} ac;

void go()
{
int n, q;
cin >> n >> q;
string s;
ac.init();
for (int i = 1; i <= n; i++)
{
cin >> s;
ac.insert(s);
}
ac.build(n);
while (q--)
{
static int l, r, k;
cin >> l >> r >> k;
cout << ac.ask(l, r, k) << endl;
}
}
捐助作者
0%