레이팅 미적용Dominik is truly a special student and he constantly enjoys playing with blue and
red cubes of different sizes.
He decided to build towers while following two peculiar rules:
• A cube directly above another cube can never be the same color as that cube.
• All cubes in the tower above some cube must be smaller in size than that
cube.
Dominik opened his toy box which contains exactly \(n\) cubes. For each \(i\) (\(1 \le i \le n\)),
Dominik has exactly one cube of size \(i\), and it is either red or blue.
Dominik got bored of stacking towers, so he came up with \(q\) difficult questions. In each question, Dominik
thinks of two numbers \(l\) and \(r\). He wants to know the minimum number of towers he must build so that
they contain only cubes whose sizes are between \(l\) and \(r\) (inclusive), and such that every tower follows his
peculiar rules. Every cube of a size between \(l\) and \(r\) must be used, i.e., placed in some tower.
Dominik has to study a lot because it’s time for midterms at the university, so he asks you for help in
answering his \(q\) questions.
In the first line, there are two natural numbers \(n\) and \(q\) (\(1 \le n\), \(q \le 1 \cdot 10^{5}\)), the number of cubes and the
number of questions.
In the second line, there is a string \(s\), where the character \(s_{i}\) represents the color of the cube of size \(i\).
Each character of the string will be either "P" or "C".
In each of the following \(q\) lines, there are two numbers \(l_{i}\) and \(r_{i}\) (\(1 \le l_{i} \le r_{i} \le n\)), the left and right
boundaries of Dominik’s query.
In \(q\) lines, print the answers to Dominik’s questions from the problem statement.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 23점 | \(1 \le n\), \(q \le 10\) |
2 | 38점 | \(1 \le n\), \(q \le 1000\) |
3 | 25점 | There will be at most 20 blue cubes. |
4 | 24점 | No additional constraints. |
7 4
PPCPPCC
1 7
1 5
3 7
4 53
3
2
26 2
CCCCCC
1 6
2 56
416 1
PPPCPCCCCCCPPPPP
1 166Clarification of the second example: All the cubes are red, so any tower that contains at least 2
cubes does not follow Dominik’s rules. It follows that each tower contains exactly 1 cube, and the answer
to each question is the number of cubes between l and r, i.e., r −l + 1.