CF587F Duff is Mad 题解

CF587F Duff is Mad

题意

• 给定 $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 然后就再也没想对过。

设 $\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})$。

代码

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;
}