题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）

考虑是怎么查询一组 $t$ 的。对给定二元组分别建立 ACAM。记 $s$ 在 $t$ 上跳时跳到的点的序列为 $p_{1, 1..k}, p_{2, 1..k}$ 然后发现一个替换 $i$ 是可以的，当且仅当存在 $j$ 使得 $p_{1,j}$ 为 $i$ 在被替换串的 ACAM上对应点的子孙，且 $p_{2, j}$ 为 $i$ 在替换串的 ACAM 上的对应点的子孙。

你发现这个东西可能不是很好维护，因为它可能需要知道能不能覆盖完整个需要被替换的区间。我们记 $\operatorname{dif}(s, t)$ 表示从 $s$ 变为 $t$ 最小需要变化的区间。那么刚刚的情况可能会导致需要替换 $[2,5]$ 但是扫到 $j=7$ 的时候有区间 $[3, 7]$ 使得修改了 $[3, 5]$。于是你可以加一维长度表示需要满足 $len \ge k$。这样是三维偏序，显然没有办法通过。

考虑怎么优化一下。这个 $len \ge p$ 也太丑了，它直接让我们的做法加了一维。发现这个东西修改的区间长度是固定的。因此对 $s_{i, 0/1}$ 按 $\operatorname{dif}$ 分类，这样就是变为要求 $\operatorname{dif}=\operatorname{dif}'$ 了。然后每次考虑 $i \in [1, n]$ 的二元组就变成矩形加单点和了，可以扔到 dfn 序上扫描线。

时间复杂度：$O(L|\Sigma|+(n+L)\log L)$。