P14363 [CSP-S 2025] 谐音替换 / replace——链上统计转子树贡献 离线二维数点

因为是赛题，场上没怎么想

首先，一个替换能解决一个询问当且仅当其不同的部分相同，且剩余部分是对应的前缀

于是最糖的做法出现了，对于每一个询问，枚举包含不同部分的子串，研究是否存在模式串对应

赛时直接hash判断相等，拿了25pts

大家都在说kmp

这时候才想起来，对应前缀相等的话，肯定能匹配到一个位置，那么就可以直接kmp，even直接AC自动机草过去

当然需要一个构造，将两个串的公共部分叠在一起，然后拿个占位符划分出来就好了

但是AC自动机的统计我不是很明确，不敢保证复杂度是对的

同理进行一个构造，但是这次我们发现一个替换是一个询问的合法替换当且仅当 它的不同部分前的部分 是不同部分前的询问的后缀 且 它的不同部分后的部分 是 不同部分后的询问的前缀，以及中间替换的相同

那么就可以想到开两棵字典树去描述这个前后缀包含的问题

那么会发现问题就变成了，一个询问对应的在两棵字典树上的节点到根的路径颜色交（一个替换的节点对应一种颜色）

本来想着这个时候暴力直接跳的话复杂度应该是对的，因为每个字符在每个字典树上只会跳一个点

但是问题在于字典树上的一个点可能对应多个串，这个时候复杂度就假了

链上的问题，虽然可以采用树链剖分之类的方式解决，但是这个问题中数颜色并不适合用树剖解决

换个角度，每个替换能产生贡献的询问应该是在它的子树内的；离线询问，搞个dfn，可以直接转化成序列上的段，就可以变成二维数点问题了

链上的统计如果转化为各节点对询问的贡献，就可以转化为子树的统计问题了

链-子树 这个关系有没有什么名词来描述？