表示言語
/ /分数: 100 点
问题陈述
露露和泰拉正在玩红色、绿色和蓝色颜料。
露露和泰拉想要画一幅由以下组成的图画 N 方形单元格排列成一行。泰拉先画了一部分,然后把剩下的交给了露露。 Terra画的图可以用字符串来表示 S 长度 N 组成 R, G, B,和 X。如果 i- 第一个字符 S is R, i第一个单元格被涂成红色;如果是的话 G,漆成绿色;如果是的话 B,被漆成蓝色;如果是的话 X,它是一个未绘制的空单元格。
露露不喜欢泰拉画的图片,所以露露决定剪掉图片的某个区间,并将该区间做成一个 完美画面。据露露介绍,一个 完美画面 是满足以下两个条件的图片。
-
每个单元格必须涂成红色、绿色和蓝色之一。
-
露露喜欢色彩缤纷的东西,因此任何两个相邻的单元格必须始终具有不同的颜色。
Lulu 可以绘制 Terra 未绘制的任何所需颜色的空单元格,也可以重新绘制 Terra 已绘制为不同颜色的单元格。
Lulu切出的区间用两个整数表示 l 和 r,表示从 l第一个单元格到 r左侧第一个单元格。对于每个 Q 剪出某个区间的方法,告诉 Lulu 必须重新绘制的最小单元格数才能使该区间成为 完美画面.
约束
- 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 行。对于每种情况,打印一行,其中包含 Lulu 必须重新绘制才能完成的最小单元格数 完美画面.
示例输入 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이면 칠해지지 않은 빈칸을 의미한다.
루루는 테라가 칠해 놓은 그림이 마음에 들지 않아 그림의 특정 구간을 잘라내어 구간을 완벽한 그림으로 만들기로 했다. 루루가 생각한 완벽한 그림은 다음 두 조건을 만족하는 그림이다.
-
모든 칸은 빨간색, 초록색, 파란색 중 하나로 칠해져야 한다.
-
루루는 알록달록한 것을 좋아하기 때문에 인접한 두 칸의 색은 항상 달라야 한다.
루루는 테라가 칠하지 않은 비어 있는 칸을 원하는 색으로 칠할 수 있고 테라가 칠했던 칸의 색을 다른 색으로 덧칠할 수도 있다.
루루가 잘라낼 구간은 두 정수 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