CF1996C.Sort

给定两个长度为 $n$ 的字符串 $a$ 和 $b$。接下来你需要（被迫）回答 $q$ 个询问。

对于每个询问，给定一个区间 $[l, r]$。每次操作，你可以选择一个整数 $i$（$l \leq i \leq r$），并将 $a_i$ 赋值为任意你想要的字符。请输出你最少需要进行多少次操作，使得 $\texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])}$。你在某个询问中对 $a$ 的操作不会影响其他询问。

对于任意字符串 $c$，$\texttt{sorted(c[l..r])}$ 表示将子串 $c_l, c_{l+1}, \ldots, c_r$ 按字典序排序后的结果。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$），分别表示字符串的长度和询问的数量。

接下来一行包含长度为 $n$ 的字符串 $a$。保证 $a$ 只包含小写拉丁字母。

接下来一行包含长度为 $n$ 的字符串 $b$。保证 $b$ 只包含小写拉丁字母。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示一次询问的区间。

保证所有测试用例中 $n$ 和 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每个询问，输出一个整数，表示你需要进行的最少操作次数。每个答案占一行。

对于第一个询问，$\texttt{sorted(a[1..5])} = $ abcde，$\texttt{sorted(b[1..5])} = $ abcde，所以不需要进行任何操作。

对于第二个询问，你需要将 $a_1$ 赋值为 e。此时，$\texttt{sorted(a[1..4])} = \texttt{sorted(b[1..4])} = $ bcde。

由 ChatGPT 4.1 翻译