← 返回题目列表

AtCoder · agc059_a

A. 我的最后一个 ABC 问题

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

分数: 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,和 C in 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).