题解

思路

所有名字在开始时固定不变，变化的只是每个编号的嫌疑值。把名字建成 AC 自动机后，查询串扫描到某个状态时，能作为当前前缀后缀出现的名字，恰好对应这个状态在 fail 树上的祖先终止结点。

因此问题转化为：支持修改某个终止结点的权值，并查询 fail 树上从根到指定状态路径的最大权值。

做法

子任务 1：逐条检查

维护每个编号的当前嫌疑值。遇到查询串时，枚举所有名字，直接判断它是否为查询串的子串，并取对应嫌疑值最大值。找不到时输出 $-1$。

子任务 2：静态 AC 自动机

这一层没有修改，所有嫌疑值始终为 $0$。建立 AC 自动机，并把“是否存在名字结尾”的标记沿失配指针传播。扫描查询串；若到达过带标记的状态就输出 $0$，否则输出 $-1$。

子任务 3：动态 fail 树根链最大值

同一名字可能对应多个编号，因此每个 Trie 终止结点维护一个多重集合，保存所有映射到该结点的当前嫌疑值。结点权值是集合最大值；修改编号时从旧集合删除旧值、插入新值。

fail 指针构成一棵树。对 fail 树做重链剖分，在线段树中按剖分序维护每个结点的权值。扫描查询串得到自动机状态后，把根到该状态的路径拆成若干条重链区间，并查询最大值。对查询串的每个字符都执行一次根链查询，所有结果的最大值就是答案。

独立核验实现使用另一种等价结构：fail 树结点的权值影响其整棵子树，按 DFS 序转化为区间插入；自动机状态只需做单点查询。区间覆盖结点使用带惰性删除的最大堆维护。

正确性说明

AC 自动机扫描到状态 $u$ 时，一个名字在当前位置结束，当且仅当它的终止结点是 $u$ 在 fail 树上的祖先。因此根到 $u$ 路径上的所有终止结点恰好、不重不漏地表示当前已出现的名字。

每个终止结点的多重集合保留了该字符串对应的全部受害者编号，集合最大值正是该名字当前可贡献的最大嫌疑值。重链剖分路径查询返回所有匹配名字的最大嫌疑值；再对查询串全部位置取最大值，就得到所有子串匹配记录的最大值。若所有根链都没有终止结点，答案保持 $-1$。

复杂度分析

设名字总长为 $S$，所有查询串总长为 $Q$。建立自动机与 fail 树为 $O(26S)$。每次修改为 $O(\log n+\log S)$；查询的每个字符需要 $O(\log^2 S)$，总复杂度为 $O(26S+(m+Q)\log^2 S)$，空间复杂度为 $O(26S+n)$。