CF163E e-Government
Codeforces Luogu 分析 建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。 我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。 再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。 代...
Codeforces Luogu 分析 建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。 我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。 再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。 代...
Codeforces Luogu 分析 考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。 将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。 代码 // =================================== /...
Luogu 分析 做完这题感觉对 AC 自动机有了新的理解... 注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。 然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串，于是我们只需要把 $Y$...