P5576 [CmdOI2019] 口头禅

· · 题解

另一种 SA 做法。

记 N=n+\sum\limits_{i=1}^n|s_i|。考虑区间 [l,r] 内的串都有长度为 L 的公共子串，则从 s_l,\dots,s_r 中各选取一个后缀，一定存在一种方案使得这些后缀存在长度为 L 的最长公共前缀。

将所有串拼起来建 SA。若把排名为 i 的后缀看作点，\text{height}_i 看作 i-1 和 i 两点间连边的权值，则若把所有边权 \ge L 的边加入链，最长公共前缀长度 \ge L 的后缀位于同一个连通块内。那么我们若判断最长公共子串长度是否 \ge L，就转化为将所有 \ge L 的边加入后，是否存在一个连通块内有来自 [l,r] 内的所有串的后缀。

称一个后缀的颜色为其来自的串的编号。对于每个连通块，考虑用 ODT 维护其中后缀极长同色连续段（下简称颜色段）。称某一时刻颜色段的权值为当前加入的边的最小值。那么一个询问就是求所有 l'\le l,r'\ge r 的颜色段 [l',r'] 的最大权值。

形式像二维偏序。如果颜色段的数量不多就好了。考虑分析颜色段的数量。

考虑启发式合并，则合并两个连通块时，较小的连通块内的颜色段插入较大的连通块的 ODT 时，仅会和大连通块中所有与其有交的颜色段取并得到一个新的颜色段。而对于无交的颜色段，她原先就存在，且在合并之后会产生一个和她端点相同但是权值更小的颜色段，显然不优，因此不用动这样的颜色段。

由于任意时刻连续段数量是不超过连通块内点数的，而每合并一次产生一个新颜色段，根据启发式合并的结论，可以得到颜色段数为 \mathcal{O}(N\log N)。

那只需要找出所有颜色段然后离线下来扫描线 + BIT 维护即可。

考虑怎么找出所有颜色段。往 ODT 中插入一个颜色段 [l',r'] 时，若其已经被包含则不用插入她。否则，二分出边界并尝试往两边扩展。具体实现看代码。

但是一个一个插入颜色段的过程中会产生一些在最终结果中并不存在的颜色段。不过由于颜色段的长度是不减的，因此这些“过程量”端点的限制一定不优，因此对最终答案无影响。

时间复杂度为 \mathcal{O}\left(N\log^2N\right)，空间复杂度为 \mathcal{O}(N\log N)。

AC Link

AC Code