分数: 500 点
问题陈述
考虑一个字符串 t 仅由字符组成 A, B,和 C。
我们可以用它进行以下操作:
- 选择任意子字符串 t[l:r] 和任何排列 (X, Y, Z) 字符数 (
A,B,C)。在这里, t[l:r] 表示由 l-th 通过 r第一个字符 t,其中 l 和 r 由您选择。然后,替换每个字符A,B,和Cin t[l:r] by X, Y,和 Z。
例如,对于字符串 t = ACBAAC,我们可以选择一个子字符串 t[3:6] 和 (X,Y,Z)=(C,B,A)。
经过此操作,字符串将变为 ACBCCA.
Alina 喜欢所有字符都相同的字符串。她定义了弦之美 t 作为使其所有字符相等所需的最少操作数。
给你一个字符串 S 长度 N 仅由字符组成 A, B,和 C。
回答 Q 查询。的 i-第一个查询如下:
- 给定整数 L_i 和 R_i,发现子串的美妙之处 t=S[L_i:R_i].
约束
- 1 \le N \le 10^5
- S 是一个长度为 N 仅由字符组成
A,B,和C. - 1 \le Q \le 10^5
- 1 \le L_i \le R_i \le N
- 输入中的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
输出
输出 Q 行。在 i第行,输出答案 i第一个查询。
示例输入 1
6 4 ABCCCA 3 5 2 3 1 3 1 6
示例输出 1
0 1 2 2
在第一个查询中,字符串是 t = CCC,其中所有字母都已经相等。答案是 0.
在第二个查询中,字符串是 t = BC。我们可以将其更改为 BB 在一次操作中,通过选择子字符串 t[2:2] 和 (X,Y,Z)=(A,C,B).
在第三个查询中,字符串是 t = ABC。我们可以将其更改为 AAB 在一次操作中,通过选择子字符串 t[2:3] 和 (X,Y,Z)=(C,A,B),然后到 BBB 在接下来的操作中,通过选择一个子字符串 t[1:2] 和 (X,Y,Z)=(B,A,C).