【题解】bzoj3881[COCI2015] Divljak

Alice 有 $n$ 个字符串 $\rm S_1,S_2,\dots,S_n$,Bob 有一个字符串集合 $\rm T$ ,一开始集合是空的。

接下来会发生 $q$ 个操作,操作有两种形式:

  1. 1 P Bob 往自己的集合里添加了一个字符串 $\rm P$。
  2. 2 x Alice 询问 Bob,集合 $\rm T$ 中有多少个字符串包含串 $\rm S_x$(我们称串 $\rm A$ 包含串 $\rm B$,当且仅当 $\rm B$ 是 $\rm A$ 的子串)。

对于 $100\%$ 的数据,$1 \leq n,q \leq 10^5$,字符串由小写字母构成,所有字符串的总长 $\le 2 \times 10^6$。

今天突然和 zay 聊起 ACAM 来,于是想到还有这道好题没整理。

啊,这题背后可是记载着光荣岁月啊…但这是只有我和 zay 知道的秘密/qq

大概是考虑,反正是匹配问题——那么是对着 $\rm T$ 建自动机呢,还是对 $\rm \{S_n\}$ 建。 考虑 AC 自动机更适合做这种匹配题,于是大概想到要拿 AC 自动机做;考虑如果对着 $\rm T$ 建自动机,树的形态会变,$\rm S$ 的信息需要动态维护,并不很好做,于是考虑对 $\rm S$ 建自动机 $\rm AC_s$。

考虑这样做,就需要在已经建好的自动机上,对于每个新加进来的 $P$ 计算贡献。那么会被 $P$ 包含的字符串,一定是 $P$ 在 $\rm AC_s$ 里匹配的 $endpos$ 到根的路径上每个点,到根的链上的点集并。暴力是 $n^2$ 的,考虑如何快速计算这个贡献,发现能做到最快的,也就是通过维护 dfs 序的方式求出点集并。对于每一个这样的链的并打一个标记。询问的时候只需要回答一下子树内有多少个点被打了不同的标记。

发现「维护树链标记」+「子树求和」,最快速的方法是维护差分。同时由于是动态的,可以想到用线段树或者 BIT 快速维护。

考虑修改如何进行。发现为了保证 $\land$ 形态的链只会被计数一次,需要在 $lca$ 处差分。此处需要注意的是,要对 $dfs$ 序排序之后,再逐个差分,方法是 $(i,+1),(i+1,+1),(lca_{i,i+1},-1)$ 。

想了半天才大约明白为什么要按 dfs 序排一遍序。大概是如果不按 dfs 序的顺序枚举,可能会出现某个子树未被成功打上标记的情况。

最终复杂度是 $O(\rm |S|\log |S|)$ 的,跑的不是很快。

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
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define Sigma 27
#define il inline
#define MAXN 2001010

using namespace std ;

char S[MAXN] ;
int T, M, N, L[MAXN] ;
struct Edge{
int to, next ;
#define to(k) E[k].to
#define next(k) E[k].next
}E[MAXN] ; int head[MAXN], base[MAXN], cnt, tot ;
int _ed[MAXN], dfn[MAXN], rgl[MAXN], rgr[MAXN], tp ;
int sz[MAXN], dep[MAXN], fa[MAXN], top[MAXN], son[MAXN], val[MAXN << 2] ;

void add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
}
void dfs(int u){
sz[u] = 1, dep[u] = dep[fa[u]] + 1 ;
for (int k = head[u] ; k ; k = next(k)){
fa[to(k)] = u, dfs(to(k)), sz[u] += sz[to(k)] ;
if (!son[u] || sz[to(k)] > sz[son[u]]) son[u] = to(k) ;
}
}
void dfs2(int u, int tp){
top[u] = tp,
dfn[u] = rgl[u] = ++ tot ;
if (son[u]) dfs2(son[u], tp) ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != son[u]) dfs2(to(k), to(k)) ;
rgr[u] = tot ;
}
il bool comp(int x, int y){ return dfn[x] < dfn[y] ; }
int lca(int u, int v){
while (top[u] != top[v]){
if (dep[top[u]] >= dep[top[v]]) u = fa[top[u]] ;
else v = fa[top[v]] ;
}
return dep[u] < dep[v] ? u : v ;
}

void _up(int rt){
val[rt] = val[rt << 1] + val[rt << 1 | 1] ;
}
void update(int rt, int l, int r, int p, int v){
if (l == r)
return val[rt] += v, void() ;
int mid = (l + r) >> 1 ;
if (mid >= p)
update(rt << 1, l, mid, p, v) ;
else update(rt << 1 | 1, mid + 1, r, p, v) ;
_up(rt) ;
}
int query(int rt, int l, int r, int pl, int pr){
if (pl > pr) return 0 ;
if (l >= pl && pr >= r) return val[rt] ;
int mid = (l + r) >> 1, res = 0 ;
if (pl <= mid) res += query(rt << 1, l, mid, pl, pr) ;
if (pr > mid) res += query(rt << 1 | 1, mid + 1, r, pl, pr) ;
return res ;
}
struct ACAM{
queue <int> q ;
int _size, fail[MAXN] ;
int trie[MAXN][Sigma] ;
void insert(char *s, int n){
int rt = 0, x ;
for (int i = 1 ; i <= L[n] ; ++ i){
x = s[i] - 'a' ;
if (!trie[rt][x])
trie[rt][x] = ++ _size ;
rt = trie[rt][x] ;
}
_ed[n] = rt ;
}
void build(){
for (int i = 0 ; i < Sigma ; ++ i)
if (trie[0][i]) q.push(trie[0][i]) ;
while (!q.empty()){
int n = q.front() ; add(fail[n], n), q.pop() ;
for (int i = 0 ; i < 26 ; ++ i){
if (!trie[n][i]) trie[n][i] = trie[fail[n]][i] ;
else fail[trie[n][i]] = trie[fail[n]][i], q.push(trie[n][i]) ;
}
}
}
void solve(char *S){
int x, rt = 0 ; tp = 0 ;
for (int i = 1 ; i <= N ; ++ i)
x = S[i] - 'a', rt = trie[rt][x], base[++ tp] = rt ;
sort(base + 1, base + tp + 1, comp),
tp = unique(base + 1, base + tp + 1) - base - 1 ;
for (int i = 1 ; i <= tp ; ++ i){
update(1, 1, tot, dfn[base[i]], 1) ;
if (i > 1) update(1, 1, tot, dfn[lca(base[i], base[i - 1])], -1) ;
}
}
}AC ;

int qr(){
int r = 0 ; char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) r = (r << 1) + (r << 3) + c - 48, c = getchar() ;
return r ;
}
int main(){
// freopen("1.in", "r", stdin) ;
// freopen("1.ans", "w", stdout) ;
cin >> T ; int m, q ;
for (int i = 1 ; i <= T ; ++ i)
scanf("%s", S + 1), L[i] = strlen(S + 1), AC.insert(S, i) ;
AC.build() ; cin >> M ; dfs(0), dfs2(0, 0) ;
// for (int i = 1 ; i <= T ; ++ i) cout << rgl[i] << " " << rgr[i] << endl ;
while (M --){
m = qr() ;
if (m == 1) scanf("%s", S + 1), N = strlen(S + 1), AC.solve(S) ;
else q = qr(),
printf("%d\n", query(1, 1, tot, 1, rgr[_ed[q]]) - query(1, 1, tot, 1, rgl[_ed[q]] - 1)) ;
}
return 0 ;
}