题解 P5840 【[COCI2015] Divljak】

~~首先给烈士搬题人上香~~ 大概是考虑，反正是匹配问题——那么是对着 $\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 快速维护。 考虑修改如何进行。发现为了保证 $\and$ 形态的链只会被计数一次，需要在 $lca$ 处差分。此处需要注意的是，要对 $dfs$ 序排序之后，再逐个差分，方法是 $(i,+1),(i+1,+1),(lca_{i,i+1},-1)$ 。 想了半天才大约明白为什么要按 dfs 序排一遍序。大概是如果不按 dfs 序的顺序枚举，可能会出现某个子树未被成功打上标记的情况。 最终复杂度是 $O(\rm |S|\log |S|)$ 的，跑的不是很快。 哦，对，`_end`是关键字，千万别忘了。 ```cpp #define Sigma 27 #define il inline #define MAXN 2000010 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] ; 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 ; } ``` 吐槽 * 为啥`lxl`常数这么小啊（ * `_end`这东西一调一上午啊qaq