T650740 字典序

给定两个长度为 $n$ 的小写字符串 $s$，$t$，你可以交换 $s$ 中相邻两个字符若干次，使得 $s$ 字典序小于 $t$，求最小的交换次数，无解输出 $-1$。

注意到 $s$ 与 $t$ 不可能通过交换满足条件，故无解输出 $-1$ 。得到 5 pts。

考虑 $s_1$，由于 $t$ 中所有字母都与 $s_1$ 不同，我们遍历 $t$ 的所有字母，直到找到第一个 $t_i \lt s_1$，如果找到，则 $i - 1$ 即为答案，否则即为 $-1$。得到 15 pts。

可以开始优雅地暴力了。暴力方法有很多，讲一种与正解有关的方法。考虑枚举交换结束后公共前缀（LCP）的长度 $len$，则每次枚举可以遍历 $s$，找到最小的一个字母并将其交换回来。这时，将找到的最小字母 $s_{min}$ 与 $t_i$ 比较。若小于，则交换后计算答案输出；若大于，则答案为 $-1$ ，也能直接输出；若相等，则继续遍历下一个 $len$。时间复杂度 $O(n^2)$。

考虑优化上面的暴力。可以发现每次只需要每个字母最靠前的一个，所以可以使用 26 个队列 $q_{'a'-'z'}$ 来存储字母的位置。同时我们不能再完整地模拟所有交换操作，注意到可以记录 $s_i$ 后面有 $sum_i$ 个在它之前已经被使用（即成为 LCP 的一部分），则在 $s_i$ 被使用时的真实下标即为 $i + sum_i$。

所以我们用树状数组记录后缀和 $sum$，从 $0$ 枚举 LCP 长度 $len$，根据 $t_{len + 1}$ 选择取 $q_c(c\in['a', t_{len + 1}))$ 的队头出来，取下标最靠前的计算需要的移动次数，得出答案当前 $len$ 的答案。然后考虑移动 $s$ 中 $q_{t_{len + 1}}$ 队头所示位置的字母到 $len$ 处，并弹出 $q_{t_{len + 1}}$ 的队头，同时在树状数组中将该位置加 $1$。时间复杂度 $O(n|\Sigma| + n\log n)$，$|\Sigma|$ 为字符集大小。