D - Coloring 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

Lulu and Terra are playing with red, green, and blue paints.

Lulu and Terra want to paint a picture consisting of N square cells arranged in a row. Terra first painted part of the picture and then handed the rest over to Lulu. The picture painted by Terra can be represented by a string S of length N consisting of R, G, B, and X. If the i-th character of S is R, the i-th cell is painted red; if it is G, it is painted green; if it is B, it is painted blue; and if it is X, it is an unpainted empty cell.

Lulu does not like the picture Terra painted, so Lulu decided to cut out a certain interval of the picture and make that interval into a perfect picture. According to Lulu, a perfect picture is a picture satisfying the following two conditions.

  1. Every cell must be painted one of red, green, and blue.

  2. Lulu likes colorful things, so any two adjacent cells must always have different colors.

Lulu can paint empty cells that Terra did not paint in any desired color, and can also repaint cells Terra has already painted in a different color.

The interval Lulu cuts out is represented by two integers l and r, meaning the consecutive interval from the l-th cell to the r-th cell from the left. For each of the Q ways to cut out a certain interval, tell Lulu the minimum number of cells that must be repainted to make the interval a perfect picture.

Constraints

  • 1 \leq N, Q \leq 300\,000
  • The string S consists only of uppercase letters R, G, B, and X.
  • For each query, 1 \leq l_i \leq r_i \leq N.
  • All given numbers are integers.

Input

The 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

Print Q lines. For each case, print one line containing the minimum number of cells Lulu must repaint to complete the perfect picture.

Sample Input 1

8 3
RRXGGGBR
1 8
4 5
2 7

Sample Output 1

2
1
1

表示言語

/ /

Score : 100 points

문제

루루와 테라는 빨간색, 초록색, 파란색 물감을 가지고 색칠 놀이를 하고 있다.

루루와 테라는 N개의 정사각형 칸이 일렬로 연결된 그림을 색칠하려 한다. 테라가 먼저 그림의 일부를 칠한 뒤 남은 부분을 루루에게 넘겨주었다. 테라가 칠한 그림은 R, G, B, X로 이루어진 길이 N의 문자열 S로 표현할 수 있다. 문자열 S의 i번째 문자가 R이면 빨간색, G이면 초록색, B이면 파란색, X이면 칠해지지 않은 빈칸을 의미한다.

루루는 테라가 칠해 놓은 그림이 마음에 들지 않아 그림의 특정 구간을 잘라내어 구간을 완벽한 그림으로 만들기로 했다. 루루가 생각한 완벽한 그림은 다음 두 조건을 만족하는 그림이다.

  1. 모든 칸은 빨간색, 초록색, 파란색 중 하나로 칠해져야 한다.

  2. 루루는 알록달록한 것을 좋아하기 때문에 인접한 두 칸의 색은 항상 달라야 한다.

루루는 테라가 칠하지 않은 비어 있는 칸을 원하는 색으로 칠할 수 있고 테라가 칠했던 칸의 색을 다른 색으로 덧칠할 수도 있다.

루루가 잘라낼 구간은 두 정수 l과 r로 표현되며, 이는 왼쪽에서 l번째 칸부터 r번째 칸까지의 연속한 구간을 의미한다. 특정 구간을 잘라내는 Q가지 경우에 대해 루루가 최소 몇 번 덧칠을 해야 완벽한 그림을 만들 수 있는지 알아내 보자.

제한

  • 1 \leq N, Q \leq 300\,000
  • 문자열 S는 대문자 R, G, B, X로만 이루어져 있다.
  • 1 \leq l_i \leq r_i \leq N
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

출력

Q개의 줄에 걸쳐 각 경우마다 루루가 완벽한 그림을 완성하는 데 필요한 덧칠의 최소 횟수를 한 줄에 하나씩 출력한다.

입력 예 1

8 3
RRXGGGBR
1 8
4 5
2 7

출력 예 1

2
1
1

表示言語

/ /

配点 : 100 点

問題文

ルルとテラは赤色，緑色，青色の絵の具で塗り絵をしている．

ルルとテラは N 個の正方形のマスが一列につながった絵を塗ろうとしている．テラが先に絵の一部を塗った後，残りの部分をルルに渡した．テラが塗った絵は R, G, B, X からなる長さ N の文字列 S で表される．文字列 S の i 番目の文字が R なら赤色，G なら緑色，B なら青色，X なら塗られていない空のマスを表す．

ルルはテラが塗った絵が気に入らず，絵の特定の区間を切り出して，その区間を 完璧な絵 にすることにした．ルルが考える 完璧な絵 とは，次の 2 つの条件を満たす絵である．

  1. すべてのマスは赤色，緑色，青色のいずれかで塗られていなければならない．

  2. ルルは色とりどりなものが好きなので，隣り合う 2 つのマスの色は常に異ならなければならない．

ルルは，テラが塗っていない空のマスを好きな色で塗ることができ，テラがすでに塗ったマスの色を別の色に塗り直すこともできる．

ルルが切り出す区間は 2 つの整数 l と r で表され，これは左から l 番目のマスから r 番目のマスまでの連続した区間を意味する．特定の区間を切り出す Q 通りの場合について，ルルが 完璧な絵 を作るために塗り直す必要があるマスの最小個数を求めよ．

制約

  • 1 \leq N, Q \leq 300\,000
  • 文字列 S は英大文字 R, G, B, X のみからなる．
  • 各クエリについて，1 \leq l_i \leq r_i \leq N
  • 入力される数値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行にわたり，各場合について，ルルが 完璧な絵 を完成させるために塗り直す必要があるマスの最小個数を 1 行に出力せよ．

入力例 1

8 3
RRXGGGBR
1 8
4 5
2 7

出力例 1

2
1
1