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

· · 题解

被 T3 创飞了qwq。

对于一对字符串，容易找出第一个不相同的位置和最后一个不相同的位置，构成一个极小替换区间 [l,r]。

对于符合的对应替换区间，字符串哈希即可。

那么就要解决区间前后同时匹配的问题，不难发现（我咋没注意到）需要匹配的是结束点在 l-1 的一段后缀和开始点在 r+1 的一段前缀。直接建两颗字典树，把询问和修改离线到其中一颗树上，在另一颗树上用树状数组维护答案。本质上是二维数点。