题解

思路

所有姓名在开始时已经给定，变化的只是每个姓名是否启用。把姓名建立成 AC 自动机。扫描询问文本到达状态 $u$ 时，在当前位置结尾的姓名，恰好是 $u$ 在 fail 树上的祖先终止结点。

因此问题转化为：启用或停用一个终止结点，并查询 fail 树根到当前状态路径上启用终止结点的数量。

做法

子任务 1：直接枚举

维护每个姓名当前是否启用。遇到询问文本时，枚举全部启用姓名，并枚举它在文本中的每个可能起点，统计所有重叠出现。

子任务 2：静态 AC 自动机

没有启用或停用操作时，所有姓名始终启用。建立 AC 自动机后，把终止计数沿 fail 指针传播。扫描文本时，当前状态的累计计数就是在当前位置结尾的姓名数量。

子任务 3：fail 树与树状数组

在 fail 树的 DFS 序中，一个结点的子树形成连续区间。若姓名终止结点为 $v$，它会对且仅会对 $v$ 子树内的自动机状态贡献一。因此启用姓名时给 $v$ 的整棵子树加一，停用时减一；扫描文本到状态 $u$ 时，查询 $u$ 的单点值即可。

使用差分树状数组实现子树区间加和单点查询。初始所有姓名均启用；另用布尔数组记录状态，从而正确忽略重复的加入或移除操作。

独立满分实现对 fail 树做重链剖分：启用状态作为终止结点点权，询问时直接求根到自动机状态的路径和。

正确性说明

AC 自动机扫描到状态 $u$ 时，姓名在当前位置结束，当且仅当该姓名的终止结点是 $u$ 在 fail 树上的祖先。等价地，$u$ 位于该终止结点的子树内。

对子树执行区间加后，状态 $u$ 的单点值正好累加了全部启用祖先终止结点的贡献，也就是当前位置结尾的启用姓名数量。对询问文本的全部位置求和，便得到所有启用姓名的全部出现次数。状态数组保证无效的重复更新不会改变贡献。

复杂度分析

设姓名总长为 $S$，询问文本总长为 $Q$。建立自动机为 $O(26S)$；每次启用或停用为 $O(\log S)$，查询总计为 $O(Q\log S)$。空间复杂度为 $O(26S+k)$。