简单题。 考虑到有个性质： 若我们已经知道串 、 长啥样，就可以用这样的方式计算最小交换次数： ，考虑令 等于 的长度为 的前缀中 的出现次数 减去 的长度为 的前缀中 的出现次数，则跨过这个位置的交换一定至少有 步。 将所有位置的最小交换次数加起来，则可得到将 变成 的最小交换次数。 注意到需要统计答案的部分只和前缀 的个数差有关，于是可以数位 ： 考虑设 表示前 个位置，此时 、 两个串 的个数差值为 ，且： 、 均贴上界 仅有 贴上界 、 均未贴上界且已经比较出大小 、 均未贴上界且没有比较出大小 时，所有合法状态的最小交换次数和。再设辅助数组 表...

yysy，这题 连 都不要，为啥要开 啊，故意放暴力过？？？ 这里是个非常弱智的做法： 随便钦定一个点为根之后，考虑将一条边的边权放在儿子节点上。 首先树剖，然后考虑修改 的点权，可以先只修改其重儿子以及其到父亲的边的边权。 然后考虑用带修主席树（树套树）维护一下区间内边权出现次数。 再然后，询问的时候跳重链，链顶都更新一下其到父亲的边权，然后更新一下带修主席树中存的东西，然后询问区间内出现次数。 然后，就是码板子的事情了。 /********************************************************************************...

写这份题解之前，还没看见有人写这个题的题解，那么我就来写个吧。不排除我眼瞎的可能性 首先，我们钦定串 为最短的 ，满足 ，再钦定 为 。 如果 ，则答案一定为 。毕竟 不可能出现在比它还短的串中。 那么，不难发现，对于 ， 都能用 和 的若干次拼接表示。 然后再经过分析，不难发现，由于 ，且 ，则 在 中，要么出现在 中，要么出现在 中，要么出现在 或者 或者 的拼接中。 举个栗子，考虑 ，，，（此处下划线为标记 的匹配位置）。 不难发现， 只在 中出现 次，在 中出现 次，在 中出现 次（这里我们认为，只有 在字符串拼接的匹配中，匹配位置包含了前一个串...