AT_agc059_a [AGC059A] My Last ABC Problem

考虑一个只由字符 `A`、`B`、`C` 组成的字符串 $t$。对于该字符串，可以进行如下操作： - 任意选择一个子串 $t[l:r]$，以及字符 $($`A`$,$`B`$,$`C`$)$ 的任意一种排列 $(X, Y, Z)$。这里，$t[l:r]$ 表示从第 $l$ 个字符到第 $r$ 个字符组成的子串，$l$ 和 $r$ 可以任意选择。然后，将 $t[l:r]$ 中的每个 `A` 替换为 $X$，每个 `B` 替换为 $Y$，每个 `C` 替换为 $Z$。 例如，对于字符串 $t = $ `ACBAAC`，可以选择子串 $t[3:6]$ 和排列 $(X, Y, Z) = ($`C`$,$`B`$,$`A`$)$。执行该操作后，字符串变为 `ACBCCA`。 阿丽娜喜欢所有字符都相同的字符串。她将字符串 $t$ 的“美丽度”定义为：将其所有字符变为相同所需的最少操作次数。 给定一个长度为 $N$、只包含字符 `A`、`B`、`C` 的字符串 $S$。请回答 $Q$ 个询问。第 $i$ 个询问如下： - 给定整数 $L_i$ 和 $R_i$，请你求出子串 $t = S[L_i:R_i]$ 的美丽度。

输入从标准输入按以下格式给出。 > $N$ $Q$ $S$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 限制条件 - $1 \leq N \leq 10^5$ - $S$ 只包含字符 `A`、`B`、`C`。 - $1 \leq Q \leq 10^5$ - $1 \leq L_i \leq R_i \leq N$ - 输入中的所有数均为整数。 ### 样例解释 1 对于第一个询问，字符串为 $t = $ `CCC`，已经全部相同，答案为 $0$。 对于第二个询问，字符串为 $t = $ `BC`，可以选择子串 $t[2:2]$ 和排列 $(X, Y, Z) = ($`A`$,$`C`$,$`B`$)$，一次操作即可变为 `BB`。 对于第三个询问，字符串为 $t = $ `ABC`，可以选择子串 $t[2:3]$ 和排列 $(X, Y, Z) = ($`C`$,$`A`$,$`B`$)$，一次操作可变为 `AAB`，再选择子串 $t[1:2]$ 和排列 $(X, Y, Z) = ($`B`$,$`A`$,$`C`$)$，第二次操作可变为 `BBB`。 由 ChatGPT 4.1 翻译