题解

思路分析

这是一道 AC自动机 + 树上启发式合并 + 树链剖分 的高级数据结构题。

问题建模

• $N$ 个喵星人，每个有姓和名（整数序列）
• $M$ 次点名，每次给一个串
• 问每次点名有多少人答到，每人答到多少次

核心思路

1. AC自动机构建

将所有点名串插入 AC自动机：

• Trie 存储所有模式串
• 构建 fail 指针
• fail 树体现了后缀关系

2. 匹配统计

对于每个喵星人的姓名串，在 AC自动机上匹配：

• 记录经过的所有节点
• 在 fail 树上，这些节点到根的路径上的模式串都被匹配

3. 树上问题转化

问题转化为：

• 对于每个喵星人，标记一些 AC自动机节点
• 统计每个模式串节点被多少人标记

使用 树上启发式合并（虚树） 优化：

• 将匹配路径上的节点按 dfn 序排序
• 用 LCA 建虚树
• 树状数组维护子树和

4. LCA + 树剖

使用树链剖分求 LCA，统计路径贡献。

算法步骤

1. 构建 AC自动机：

   • 插入所有点名串
   • 构建 fail 指针
   • 建立 fail 树

2. 树剖预处理：

   • DFS 求重链
   • 建立 dfn 序

3. 匹配统计：

   • 对每个喵星人的姓名匹配
   • 记录虚树节点
   • 树状数组统计

4. 输出答案：

   • 每个点名串查询子树和
   • 每个喵星人查询答到次数

复杂度分析

• AC自动机构建：$O(L)$，$L$ 为总长度
• 匹配：$O(L \log n)$
• 总时间复杂度：$O(L \log L)$
• 空间复杂度：$O(L)$

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5 + 5;

std::vector<int> G[N];

struct ACAM {
	std::map<int, int> trie[N];
	int tot, idx[N], fail[N], end[N];

	void insert(const std::basic_string<int> & s, int id) {
		int u = 0;
		for (auto v : s) {
			if (trie[u].find(v) == trie[u].end()) trie[u][v] = ++tot;
			u = trie[u][v];
		}
		end[u]++, idx[id] = u;
	}

	void build() {
		std::queue<int> q;
		for (auto [v, i] : trie[0]) {
			q.push(i);
		}
		
		while (!q.empty()) {
			int u = q.front();
			q.pop();

			for (auto [c, v] : trie[u]) {
				int j = fail[u];
				while (j > 0 && trie[j].find(c) == trie[j].end()) j = fail[j];
				if (trie[j].find(c) != trie[j].end()) fail[v] = trie[j][c];
				q.push(v);
			}
		}

		for (int i = 1; i <= tot; i++) {
			G[fail[i]].push_back(i);
		}
	}

	size_t size() const {
		return tot + 1;
	}
}ACAM;

int n, m;
int sum[N];
int dep[N], siz[N], son[N], fa[N];
void dfs1(int u) {
	son[u] = -1;
	siz[u] = 1;

	for (auto v : G[u]) {
		fa[v] = u, dep[v] = dep[u] + 1, sum[v] = sum[u] + ACAM.end[v];
		dfs1(v);
		siz[u] += siz[v];
		if (son[u] == -1 || siz[v] > siz[son[u]]) {
			son[u] = v;
		}
	}
}

int top[N], dfn[N], dfn_cnt;
void dfs2(int u, int x) {
	top[u] = x;
	dfn[u] = ++dfn_cnt;
	if (son[u] != -1) dfs2(son[u], x);
	for (auto v : G[u]) {
		if (v != son[u]) {
			dfs2(v, v);
		}
	}
}

int LCA(int u, int v) {
	for (; top[u] != top[v]; u = fa[top[u]]) {
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
	}
	return dep[u] < dep[v]? u: v;
}

std::basic_string<int> s[N];
int ans[N];

struct BIT {
	int t[N];
	size_t n;
	void resize(const size_t & _sz = 0) {
		memset(t, 0, sizeof(int) * (_sz + 1));
		n = _sz;
	}

	int lowbit(int x) const {
		return x & -x;
	}
	void update(int x, int val) {
		for (; x <= n; x += lowbit(x)) {
			t[x] += val;
		}
	}
	int query(int x) {
		int ans = 0;
		for (; x; x -= lowbit(x)) ans += t[x];
		return ans;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}t;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int l;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			s[i] += x;
		}
		s[i] += -1;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			s[i] += x;
		}
	}

	for (int i = 1; i <= m; i++) {
		std::basic_string<int> t;
		int l;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			t += x;
		}
		ACAM.insert(t, i);
	}

	ACAM.build();
	t.resize(ACAM.size());
	dfs1(0), dfs2(0, 0);

	for (int i = 1; i <= n; i++) {
		std::vector<int> vec;
		int u = 0;
		for (auto c : s[i]) {
			while (u > 0 && ACAM.trie[u].find(c) == ACAM.trie[u].end()) {
				u = ACAM.fail[u];
			}
			if (ACAM.trie[u].find(c) != ACAM.trie[u].end()) u = ACAM.trie[u][c];
			vec.push_back(u);
		}
		std::sort(vec.begin(), vec.end(), [&](const int & x, const int & y) {
			return dfn[x] < dfn[y];
		});
		t.update(dfn[vec[0]], 1);
		ans[i] += sum[vec[0]];
		for (int j = 1; j < (int)vec.size(); j++) {
			int lca = LCA(vec[j], vec[j - 1]);
			ans[i] += sum[vec[j]], ans[i] -= sum[lca];
			t.update(dfn[vec[j]], 1), t.update(dfn[lca], -1);
		}
	}

	for (int i = 1; i <= m; i++) {
		int u = ACAM.idx[i];
		std::cout << t.query(dfn[u], dfn[u] + siz[u] - 1) << "\n";
	}

	for (int i = 1; i <= n; i++) {
		std::cout << ans[i] << " \n"[i == n];
	}
	return 0;
}

题解

把老师要读的串建成 AC 自动机，idx[i] 记录第 i 个点名串在自动机中的结点。失配指针构成一棵树，第一次 DFS 计算各结点的深度、子树大小以及 sum[u]——表示从根走到 u 时匹配到的模式串数量；第二次 DFS 进行重链剖分，得到每个结点的 dfn 和重链顶部，便于我们在失配树上做 LCA 和子树查询。

对每个喵星人，把姓与名中间插入一个不会在其它字符串出现的哨兵值后拼接成一个序列，沿 AC 自动机逐字符转移，把走到的结点按 dfn 序排序，并依次加入树状数组：遇到一条新路径时在当前结点加一，在前一个结点与当前结点的 LCA 处减一，这样可以用差分方式维护当前有哪些模式出现过；同时利用预处理好的 sum[u] 就能把该喵星人被点到的次数累加到 ans[i]。处理完全部人名后，只需对每个点名串查询其对应结点子树上的计数和，就可以得到回答该次点名的喵星人数。最后输出所有点名串的结果以及每个喵星人累计被点到的次数。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5 + 5;

std::vector<int> G[N];

struct ACAM {
	std::map<int, int> trie[N];
	int tot, idx[N], fail[N], end[N];

	void insert(const std::basic_string<int> & s, int id) {
		int u = 0;
		for (auto v : s) {
			if (trie[u].find(v) == trie[u].end()) trie[u][v] = ++tot;
			u = trie[u][v];
		}
		end[u]++, idx[id] = u;
	}

	void build() {
		std::queue<int> q;
		for (auto [v, i] : trie[0]) {
			q.push(i);
		}
		
		while (!q.empty()) {
			int u = q.front();
			q.pop();

			for (auto [c, v] : trie[u]) {
				int j = fail[u];
				while (j > 0 && trie[j].find(c) == trie[j].end()) j = fail[j];
				if (trie[j].find(c) != trie[j].end()) fail[v] = trie[j][c];
				q.push(v);
			}
		}

		for (int i = 1; i <= tot; i++) {
			G[fail[i]].push_back(i);
		}
	}

	size_t size() const {
		return tot + 1;
	}
}ACAM;

int n, m;
int sum[N];
int dep[N], siz[N], son[N], fa[N];
void dfs1(int u) {
	son[u] = -1;
	siz[u] = 1;

	for (auto v : G[u]) {
		fa[v] = u, dep[v] = dep[u] + 1, sum[v] = sum[u] + ACAM.end[v];
		dfs1(v);
		siz[u] += siz[v];
		if (son[u] == -1 || siz[v] > siz[son[u]]) {
			son[u] = v;
		}
	}
}

int top[N], dfn[N], dfn_cnt;
void dfs2(int u, int x) {
	top[u] = x;
	dfn[u] = ++dfn_cnt;
	if (son[u] != -1) dfs2(son[u], x);
	for (auto v : G[u]) {
		if (v != son[u]) {
			dfs2(v, v);
		}
	}
}

int LCA(int u, int v) {
	for (; top[u] != top[v]; u = fa[top[u]]) {
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
	}
	return dep[u] < dep[v]? u: v;
}

std::basic_string<int> s[N];
int ans[N];

struct BIT {
	int t[N];
	size_t n;
	void resize(const size_t & _sz = 0) {
		memset(t, 0, sizeof(int) * (_sz + 1));
		n = _sz;
	}

	int lowbit(int x) const {
		return x & -x;
	}
	void update(int x, int val) {
		for (; x <= n; x += lowbit(x)) {
			t[x] += val;
		}
	}
	int query(int x) {
		int ans = 0;
		for (; x; x -= lowbit(x)) ans += t[x];
		return ans;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}t;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int l;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			s[i] += x;
		}
		s[i] += -1;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			s[i] += x;
		}
	}

	for (int i = 1; i <= m; i++) {
		std::basic_string<int> t;
		int l;
		std::cin >> l;
		for (int j = 1; j <= l; j++) {
			int x;
			std::cin >> x;
			t += x;
		}
		ACAM.insert(t, i);
	}

	ACAM.build();
	t.resize(ACAM.size());
	dfs1(0), dfs2(0, 0);

	for (int i = 1; i <= n; i++) {
		std::vector<int> vec;
		int u = 0;
		for (auto c : s[i]) {
			while (u > 0 && ACAM.trie[u].find(c) == ACAM.trie[u].end()) {
				u = ACAM.fail[u];
			}
			if (ACAM.trie[u].find(c) != ACAM.trie[u].end()) u = ACAM.trie[u][c];
			vec.push_back(u);
		}
		std::sort(vec.begin(), vec.end(), [&](const int & x, const int & y) {
			return dfn[x] < dfn[y];
		});
		t.update(dfn[vec[0]], 1);
		ans[i] += sum[vec[0]];
		for (int j = 1; j < (int)vec.size(); j++) {
			int lca = LCA(vec[j], vec[j - 1]);
			ans[i] += sum[vec[j]], ans[i] -= sum[lca];
			t.update(dfn[vec[j]], 1), t.update(dfn[lca], -1);
		}
	}

	for (int i = 1; i <= m; i++) {
		int u = ACAM.idx[i];
		std::cout << t.query(dfn[u], dfn[u] + siz[u] - 1) << "\n";
	}

	for (int i = 1; i <= n; i++) {
		std::cout << ans[i] << " \n"[i == n];
	}
	return 0;
}