回头补字符串(从SAM开始)
# 题面
给定一个长度为 $n$ 的 01 字符串 $S$,记以 $i$ 位置结束的前缀为 $S[i]$。
给定 $m$ 组询问,每组询问给出 $l,r$,求
数据规模:$n,m\le 10^5$。
# 解析
考虑建出 SAM,记 SAM 上代表前缀 $i$ 的节点为 $p_i$,则有 $\operatorname{LCS}(S[i],S[j])$ 为 parent 树上 $p_i,p_j$ 的 LCA 代表的最长字符串长度。
由此分析以下两种做法。
- SOLUTION 1. 启发式合并
考虑在 parent 树上由子树向上合并。
用 set
维护出子树 $i$ 中包含了哪些前缀,记这个集合为 $E_i$,合并只需将子节点 $v$ 的 $E_v$ 与父节点 $u$ 的 $E_u$ 合并后的结果赋给新的 $E_u$ 即可。
通过启发式合并,每次暴力将较小的集合中的元素插入较大集合,可以做到 $\mathcal{O}(n\log^2n)$。
再考虑如何计算答案。当子节点 $v$ 的信息合并到父节点 $u$ 上时,考虑每对 $(i,j)$:$i\in E_v$, $j\in E_u$;$p_i,p_j$ 的 LCA 就是点 $u$。
显然每对 $(i,j)$ 的 LCS 可以贡献到满足 $l\le \min\{i,j\}< \max\{i,j\}\le r$ 的询问 $(l,r)$。
那么我们只需要合并时记录下三元组 $(i,j,x)$,表示 $LCS(S[i],S[j])=x$。对询问离线,two-point + 树状数组 即可回答询问。
但是我们发现三元组的数量是 $\mathcal{O}(n^2)$ 的,不能接受。观察之前的过程,发现许多三元组是无用的——
在合并 $E_u,E_v$ 时,对于每个 $i\in E_u$,我们只需要找到 $E_v$ 中 $i$ 的 “前驱” 和 “后继” $j$。因为比前驱更小的 $j$,其能够贡献到的 $(l,r)$ 的范围更小,比后继更大的 $j$ 同理。
合并次数是 $\mathcal{O}(n\log n)$,于是三元组的数量也是 $\mathcal{O}(n\log n)$。
用 two-point + 树状数组,具体地:
- 将询问 $(l,r)$ 挂在 $r$;
- 从左到右枚举右端点 $r_0$,枚举三元组 $(l_0,r_0,x_0)$,更新 $l< l_0$ 的询问的答案与 $x_0$ 取 max;
- 因为取 max 不存在删除操作,也就不必要讨论树状数组无可减性的限制,只需树状数组维护后缀 max 即可回答挂在 $r$ 的询问。
复杂度也是 $\mathcal{O}(n\log^2n)$。
- SOLUTION 2. LCT
同样对询问离线,将 $(l,r)$ 挂在 $r$ 处。
考虑一种求树上 LCA 的方法。求 $u,v$ 的 LCA,可以将根到 $u$ 的路径上打上 $u$ 的标记,然后从 $v$ 向上爬,找到第一个有 $u$ 的标记的点,即为 LCA。
于是我们可以这样解决这个问题:
- 从左到右加入右端点 $r$;
- 从 $p_r$ 开始向根爬,对路上找到的每个标记 $l$,同样记录三元组 $(l,r,x)$ 表示 $LCS(S[i],S[j])=x$;
- 将 $p_r$ 到根的路径打上 $r$ 的标记。
但是显然一个点上会被盖很多标记,这样复杂度就不优了。
实际上我们只需要保留每个点上最大的标记,和 SOLUTION 1 一样的道理,因为与 $p_r$ LCA 相同的 $p_l$ 只有 $l$ 最大的能够贡献到的询问是最多的。
因为我们是从小到大插入 $r$,保留最大的就相当于直接覆盖。
然后考虑如何实现这个过程,不妨观察一下……
这不是 LCT 的 access
操作吗?
所以直接用 LCT,就可以同时找到链上的标记,以及给链打标记了。
# 源代码
- 启发式合并
点击展开/折叠代码
1 | /*Lucky_Glass*/ |
- LCT
点击展开/折叠代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
(天地虽大)水中明月又一片
(其化均也)心上尘埃只一叶
(万物虽多)提指拈花却一线
(其治一也)恍然一念间
(四达通流)欸乃渔谣隔一涧
(无所不及)跌宕石中叩一焰
(孰守无心)万化兴衰皆成镜鉴
(动以天行)照霜天
——《万象霜天(Vocaloid全员)》By 伊水 / 流绪 / Creuzer
> Link 万象霜天-Bilibili