/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
文字 A, B, C のみからなる文字列 t を考えます。
これに対し、以下の操作を行えます。
- 任意の部分文字列 t[l:r] と文字 (
A,B,C) の任意の並べ替え (X, Y, Z) を選ぶ。ここで、t[l:r] は t の l 文字目から r 文字目までで形成される部分文字列であり、l と r を選べる。そして、t[l:r] の各文字A,B,Cをそれぞれ X, Y, 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] の美しさを求めよ。
制約
- 1 \le N \le 10^5
- S は文字
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 です。これは、部分文字列 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 に変えることができます。
Score : 500 points
Problem Statement
Consider a string t consisting only of characters A, B, and C.
We can do the following operation with it:
- Choose any substring t[l:r] and any permutation (X, Y, Z) of characters (
A,B,C). Here, t[l:r] denotes the substring formed by the l-th through the r-th characters of t, where l and r are of your choice. Then, replace each characterA,B, andCin t[l:r] by X, Y, and Z, respectively.
For example, for a string t = ACBAAC, we can choose a substring t[3:6] and (X,Y,Z)=(C,B,A).
After this operation, the string will become ACBCCA.
Alina likes strings in which all characters are the same. She defines the beauty of a string t as the minimum number of operations required to make all its characters equal.
You are given a string S of length N consisting only of characters A, B, and C.
Answer Q queries. The i-th query is the following:
- Given integers L_i and R_i, find the beauty of the substring t=S[L_i:R_i].
Constraints
- 1 \le N \le 10^5
- S is a string of length N consisting only of characters
A,B, andC. - 1 \le Q \le 10^5
- 1 \le L_i \le R_i \le N
- All numbers in the input are integers.
Input
Input is given from Standard Input in the following format:
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
Output
Output Q lines. In the i-th line, output the answer to the i-th query.
Sample Input 1
6 4 ABCCCA 3 5 2 3 1 3 1 6
Sample Output 1
0 1 2 2
In the first query, the string is t = CCC, in which all letters are already equal. The answer is 0.
In the second query, the string is t = BC. We can change it to BB in one operation, by choosing a substring t[2:2] and (X,Y,Z)=(A,C,B).
In the third query, the string is t = ABC. We can change it to AAB in one operation, by choosing a substring t[2:3] and (X,Y,Z)=(C,A,B), and then to BBB in the next operation, by choosing a substring t[1:2] and (X,Y,Z)=(B,A,C).