E1神秘做法是否可以优化

学术版

StеlІаwіnD @ 2026-02-12 01:48:13

考虑在每次转移的时候枚举下一次修改的位置是哪个，改成什么字符，最远能匹配多远

我算这个匹配写了个log^3，就是二分答案，里面在SA上二分位置，和SA里面某一项比较字典序的时候二分LCP长度

总的时间复杂度是26mlog^2mlogn

然后它跑的飞慢

这个东西有优化的可能性吗

by haoertiansuo @ 2026-02-12 02:13:54

每次在不修改就能走到的位置里随机 600 个，实测可过

by XZhuRen @ 2026-02-12 02:32:08

这样可以做吗：

枚举修改点 p。

对 s,t 建立正反 GSAM，正的 SAM 从 p-1 跳链找到最浅的点 u 满足覆盖 l，然后反的 SAM 从 p+1 跳链，二分最深的点 v 使得两个子树 s 的 edp 集合有交（反 SAM 下标 -2）。

这个如果没有正确性问题应该是可以主席树+dsu on tree+二分暴力查询，时空双老哥？