← 返回题目列表

Codeforces · 1996/C

C. 排序

中文机器翻译题面 查看原题

给定两个字符串 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。然后,您(被迫)回答 $$$q$$$ 查询。

对于每个查询,都会给出一个以 $$$l$$$ 和 $$$r$$$ 为界的范围。在一次操作中,您可以选择一个整数 $$$i$$$ ($$$l \leq i \leq r$$$) 并设置 $$$a_i = x$$$,其中 $$$x$$$ 是您想要的任何字符。输出必须执行的最少操作数,使得 $$$\texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])}$$$。您对一个查询执行的操作不会影响其他查询。

对于任意字符串 $$$c$$$,$$$\texttt{sorted(c[l..r])}$$$ 表示由按字典顺序排序的字符 $$$c_l, c_{l+1}, ... , 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$$$。

输出

对于每个查询,输出一个整数,即需要在新行中执行的最少操作数。

示例

输入 #1

3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6

输出 #1

0
1
0
2
2
1
1
0

注意

对于第一个查询, $$$\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。