P8571 [JRKSJ R6] Dedicatus545

又是一道数据结构组合题，起码不是套娃题（指树套树套...）

首先，询问一个串中多个串的出现次数之类，肯定是 ACAM。询问就是求所有询问串的末尾节点的子树包含的匹配串节点的最大值。

发现有 \(\sum |S|\) 限制，纯纯的根号分治。

\(|S|>B\)，\(O(n)\) 算一遍各串在询问串里的出现次数，线段树维护。

只用考虑 \(|S|\leq B\)。

Solution 1

插入询问串时，在 dfn 序上把它的子树都分进它这一组，如果询问串末尾节点本来就属于一组了，就不标记子树。回答询问时就是把匹配串上的点拿出来，根据之前的分组把点扔到桶里，最后对每个桶取 max。

第二部分修改 \(n\log{n}\) 次，询问 \(n \sqrt{n}\) 次。

实在不行搞点抽象多重分块，分三层可以搞成修改 \(O(n^{0.25})\)。

Solution 2

把匹配串点拉出来建虚树，我们对按照子树内的匹配串点数量对所有子树排序，从多到少枚举子树，判断从子树根到原树根的路径上是否有询问串。单点加链查询转化成区间加单点查询。发现区间加可以只用区间覆盖代替，赋 1 表示有覆盖就行了。用 bitset 维护除个 w。