题解 CF587F 【Duff is Mad】
xht
2020-01-25 18:13:06
> [CF587F Duff is Mad](https://codeforces.com/contest/587/problem/F)
## 题意
- 给定 $n$ 个字符串 $s_{1 \dots n}$。
- $q$ 次询问 $s_{l \dots r}$ 在 $s_k$ 中出现了多少次。
- $n,q,\sum_{i=1}^n |s_i| \le 10^5$。
## 题解
~~一眼看成 [CF547E Mike and Friends](https://www.luogu.com.cn/problem/CF547E) 然后就再也没想对过。~~
设 $\sum_{i=1}^n |s_i| = m$。
首先建出 AC 自动机，那么答案可以表示为：
在 fail 树上，将 $s_{l \dots r}$ 的最后一个节点的子树内所有点的权值 $+1$ 后，$s_k$ 的所有节点的权值和。
考虑离线 + 根号分治，给定一个限制 $T$。
若 $|s_k| > T$，则这样的串最多只有 $\mathcal O(\frac mT)$ 个，可以对于每个 $s_k$ 线性处理。
先将 $s_k$ 的所有节点的贡献设为 $1$，然后求出子树贡献和，即每个点的权值 $+1$ 后对答案的贡献。
按顺序扫过 $n$ 个串，每扫到一个串就加上对应的贡献，那么每个询问可以作差得到。
时间复杂度为 $\mathcal O(\frac {m^2}T + q \log q)$。
若 $|s_k| \le T$，可以对每个询问 $\mathcal O(|s_k|)$ 处理。
按顺序扫过 $n$ 个串，每扫到一个串就将其最后一个节点的子树内的所有点的权值 $+1$，处理询问的时候直接暴力求。
这两种操作实际上相当于在 dfs 序上区间加和单点查，树状数组即可。
时间复杂度为 $\mathcal O(n \log m + qT \log m)$，如果树状数组改成分块的话则可以做到 $\mathcal O(n \sqrt m + qT)$。
那么总时间复杂度为 $\mathcal O(\frac {m^2}T + q \log q + n \log m + qT \log m)$，取 $T = \frac {m}{\sqrt {q \log m}}$ 时达到最优复杂度 $\mathcal O(n \log m + q \log q + m \sqrt {q \log m})$。
## 代码
```cpp
const int N = 1e5 + 7;
int n, m, q, T, len[N], S[N], c[N], dfn[N], num;
ll ans[N];
int trie[N][27], fail[N], fa[N], ed[N], tot = 1;
char s[N];
vi e[N];
vector<pi> L[N], R[N], le[N], ri[N];
queue<int> Q;
void dfs1(int x) {
for (auto y : e[x]) dfs1(y), S[x] += S[y];
}
void dfs2(int x) {
S[x] = 1, dfn[x] = ++num;
for (auto y : e[x]) dfs2(y), S[x] += S[y];
}
inline void add(int x, int k) {
while (x <= num) c[x] += k, x += x & -x;
}
inline int ask(int x) {
int k = 0;
while (x) k += c[x], x -= x & -x;
return k;
}
int main() {
rd(n), rd(q);
for (int i = 1; i <= n; i++) {
rds(s, len[i]), m += len[i];
int p = 1;
for (int j = 1; j <= len[i]; j++) {
int c = s[j] - 'a';
if (!trie[p][c]) trie[p][c] = ++tot, fa[tot] = p;
p = trie[p][c];
}
ed[i] = p;
}
for (int i = 0; i < 26; i++)
if (trie[1][i]) fail[trie[1][i]] = 1, Q.push(trie[1][i]);
else trie[1][i] = 1;
while (Q.size()) {
int x = Q.front();
Q.pop();
for (int i = 0; i < 26; i++)
if (trie[x][i])
fail[trie[x][i]] = trie[fail[x]][i], Q.push(trie[x][i]);
else trie[x][i] = trie[fail[x]][i];
}
for (int i = 2; i <= tot; i++) e[fail[i]].pb(i);
T = m / sqrt(q * log2(m));
for (int i = 1, l, r, k; i <= q; i++) {
rd(l), rd(r), rd(k);
if (len[k] > T) L[k].pb(mp(l, i)), R[k].pb(mp(r, i));
else le[l].pb(mp(k, i)), ri[r].pb(mp(k, i));
}
for (int i = 1; i <= n; i++)
if (len[i] > T) {
int p = ed[i];
while (p != 1) S[p] = 1, p = fa[p];
dfs1(1);
sort(L[i].begin(), L[i].end());
reverse(L[i].begin(), L[i].end());
sort(R[i].begin(), R[i].end());
reverse(R[i].begin(), R[i].end());
ll o = 0;
for (int j = 1; j <= n; j++) {
while (L[i].size() && L[i].back().fi == j)
ans[L[i].back().se] -= o, L[i].pop_back();
o += S[ed[j]];
while (R[i].size() && R[i].back().fi == j)
ans[R[i].back().se] += o, R[i].pop_back();
}
for (int i = 2; i <= tot; i++) S[i] = 0;
}
dfs2(1);
for (int i = 1; i <= n; i++) {
for (pi o : le[i]) {
int p = ed[o.fi];
while (p != 1) ans[o.se] -= ask(dfn[p]), p = fa[p];
}
add(dfn[ed[i]], 1), add(dfn[ed[i]] + S[ed[i]], -1);
for (pi o : ri[i]) {
int p = ed[o.fi];
while (p != 1) ans[o.se] += ask(dfn[p]), p = fa[p];
}
}
for (int i = 1; i <= q; i++) print(ans[i]);
return 0;
}
```