「模拟测试」背单词-AC 自动机+二进制分组

要求支持 $2$ 种操作:

  1. 向字典中加入一个串 $s$,其权值为 $v$(若重复算作多个串)。
  2. 询问一个串 $t$,其中在字典中出现过的单词的权值和(相同单词应被多次计算)。

强制在线。

题解

若没有强制在线,且 $2$ 在 $1$ 之后,那么我们直接建出 AC 自动机跑一遍就完了。

考虑强制在线,我们二进制分组,建出 $\log n$ 个 AC 自动机,一种好写的方法是类似树状数组,设当前字典大小为 idx,则我们从 begin = idx - (idx & -idx) + 1 开始重建,同时由于每次建 AC 自动机时,root 总是先分配内存,而且后加入的节点在内存池中连续,我们就可以 $O(1)$ 将当前内存池的指针指向 root[begin] 前,这样就可以轻松且常数更小地完成内存回收。

询问的时候,类似树状数组,在 $\log n$ 个 AC 自动机上询问即可。

时间复杂度 $O(|\Sigma||\sum S| \log |\sum S|)$,$|\Sigma|$ 为字符集大小 $26$。

代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
/**
* Copyright (c) 2017-2018, xehoth
* All rights reserved.
* words 16-01-2018
* AC 自动机 + 二进制分组
* @author xehoth
*/
#include <bits/stdc++.h>
namespace {
inline char read() {
static const int IN_LEN = 1 << 18 | 1;
static char buf[IN_LEN], *s, *t;
return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)),
s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig && (x = -x);
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1 << 18 | 1;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
(oh == obuf + OUT_LEN) && (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf);
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[21], cnt;
if (x != 0) {
(x < 0) && (print('-'), x = -x);
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
} else {
print('0');
}
}
struct InputOutputStream {
~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
} io;
typedef unsigned long long ulong;
const int MAXN = 100000 + 9;
const int SIGMA = 26;
char *cur;
const int MAXM = 2000000 + 9;
char buc[MAXN], *s[MAXN];
int idx, val[MAXN];
int n, type;
struct AhoCorasickAutomation {
struct Node {
static const int NODE_SIZE;
Node *fail, *c[SIGMA];
ulong val;
inline void *operator new(size_t) { return cur += NODE_SIZE; }
};
Node *null, *root;
inline void init(Node *p) {
p->fail = null;
for (register int i = 0; i < SIGMA; i++) p->c[i] = null;
}
inline void init() {
root = new Node();
null = new Node();
null->fail = null;
for (register int i = 0; i < SIGMA; i++) null->c[i] = root;
init(root);
}
inline void insert(int w) {
register Node *p = root;
for (register char *c = s[w]; *c; c++) {
if (p->c[*c - 'a'] == null) init(p->c[*c - 'a'] = new Node());
p = p->c[*c - 'a'];
}
p->val += val[w];
}
inline void build() {
std::queue<Node *> q;
q.push(root);
for (register Node *p, *u; !q.empty();) {
p = q.front();
q.pop();
for (register int i = 0; i < SIGMA; i++) {
if (p->c[i] != null) {
for (u = p->fail; u->c[i] == null;) u = u->fail;
p->c[i]->fail = u->c[i];
q.push(p->c[i]);
p->c[i]->val += u->c[i]->val;
} else {
p->c[i] = p->fail->c[i];
}
}
}
}
inline long long query() {
register long long ret = 0;
register Node *p = root;
for (register char *c = buc; *c; c++) {
p = p->c[*c - 'a'];
ret += p->val;
}
return ret;
}
} d[MAXN];
const int AhoCorasickAutomation::Node::NODE_SIZE =
sizeof(AhoCorasickAutomation::Node);
char pool[MAXM * AhoCorasickAutomation::Node::NODE_SIZE];
inline void build() {
register int begin = idx - (idx & -idx) + 1;
if (begin < idx)
cur = (char *)d[begin].root - AhoCorasickAutomation::Node::NODE_SIZE;
d[idx].init();
for (register int i = begin; i <= idx; i++) d[idx].insert(i);
d[idx].build();
}
inline long long query() {
register long long ret = 0;
for (register int k = idx; k; k ^= k & -k) ret += d[k].query();
return ret;
}
inline void solve() {
cur = pool;
io >> n >> type;
register long long ans = 0;
for (register int cmd, len; n--;) {
io >> cmd;
len = read(buc);
if (type) {
for (register int i = 0; i < len; i++)
buc[i] = ((buc[i] - 'a') ^ ans) % 26 + 'a';
}
switch (cmd) {
case 0: {
s[++idx] = new char[len + 1]();
memcpy(s[idx], buc, len);
io >> val[idx];
build();
break;
}
case 1: {
ans = query();
io << ans << '\n';
break;
}
}
}
}
} // namespace
int main() {
// freopen("sample/1.in", "r", stdin);
solve();
return 0;
}
分享到