/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は、白い石と黒い石を 1 列に N 個並べています。
左から i 番目の石の色は文字列 S の i 文字目で表され、白い石は W、黒い石は B に対応します。
連続区間 [l, r]（1 \leq l \leq r \leq N）とは、左から l 番目から r 番目までの石の並びを指します。
連続区間に含まれるすべての石を取り出し、好きな順序で 1 列に並べ直すことを考えます。隣り合うどの 2 つの石も異なる色であるような並べ方が存在するとき、その連続区間を よい区間 と呼びます。
特に、長さ 1 の連続区間は常によい区間です。
青木君は Q 個の質問をします。
i 番目の質問では、整数 L_i, R_i が与えられます。
各質問について、L_i \leq l \leq r \leq R_i を満たす連続区間 [l, r] のうち、よい区間であるものの個数を求めてください。
制約
- 1 \leq N \leq 5 \times 10^4
- 1 \leq Q \leq 5 \times 10^4
- S は
WとBのみからなる長さ N の文字列である - 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
- N, Q, L_i, R_i はすべて整数である
入力
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
1 行目には、石の個数 N と質問の個数 Q がスペース区切りで与えられる。
2 行目には、各石の色を表す長さ N の文字列 S が与えられる。
続く Q 行のうち i 行目には、i 番目の質問を表す整数 L_i, R_i がスペース区切りで与えられる。
出力
Q 行出力せよ。
i 行目には、i 番目の質問に対するよい区間の個数を出力せよ。
入力例 1
5 4 WBWBW 1 5 2 4 1 1 3 5
出力例 1
15 6 1 6
入力例 2
6 5 WWWWWW 1 6 1 3 2 2 3 6 5 6
出力例 2
6 3 1 4 2
入力例 3
18 8 WWBBWBWBBWWBWBWBWW 1 18 1 6 3 10 5 15 8 18 2 2 7 13 11 17
出力例 3
145 18 28 61 55 1 25 28
入力例 4
50 15 WBWBWBBBWWBBWBWBWWWBBBWBWBBWBWWBWBWBBWWBWBWBWWBBBW 1 50 1 10 11 20 21 30 31 40 41 50 5 25 10 35 15 45 2 49 7 7 18 22 24 37 33 50 3 14
出力例 4
875 41 39 42 51 45 171 270 397 809 1 10 90 146 52
入力例 5
1 1 B 1 1
出力例 5
1
Score : 466 pts
Problem Statement
Takahashi has arranged N white and black stones in a row.
The color of the i-th stone from the left is represented by the i-th character of the string S, where W corresponds to a white stone and B corresponds to a black stone.
A contiguous interval [l, r] (1 \leq l \leq r \leq N) refers to the sequence of stones from the l-th to the r-th from the left.
Consider taking out all the stones in a contiguous interval and rearranging them in a row in any order you like. If there exists an arrangement such that every two adjacent stones have different colors, we call that contiguous interval a good interval.
In particular, a contiguous interval of length 1 is always a good interval.
Aoki asks Q questions.
In the i-th question, integers L_i, R_i are given.
For each question, find the number of good intervals among the contiguous intervals [l, r] satisfying L_i \leq l \leq r \leq R_i.
Constraints
- 1 \leq N \leq 5 \times 10^4
- 1 \leq Q \leq 5 \times 10^4
- S is a string of length N consisting only of
WandB - 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
- N, Q, L_i, R_i are all integers
Input
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
The first line contains the number of stones N and the number of questions Q, separated by a space.
The second line contains a string S of length N representing the color of each stone.
The i-th of the following Q lines contains the integers L_i, R_i representing the i-th question, separated by a space.
Output
Print Q lines.
The i-th line should contain the number of good intervals for the i-th question.
Sample Input 1
5 4 WBWBW 1 5 2 4 1 1 3 5
Sample Output 1
15 6 1 6
Sample Input 2
6 5 WWWWWW 1 6 1 3 2 2 3 6 5 6
Sample Output 2
6 3 1 4 2
Sample Input 3
18 8 WWBBWBWBBWWBWBWBWW 1 18 1 6 3 10 5 15 8 18 2 2 7 13 11 17
Sample Output 3
145 18 28 61 55 1 25 28
Sample Input 4
50 15 WBWBWBBBWWBBWBWBWWWBBBWBWBBWBWWBWBWBBWWBWBWBWWBBBW 1 50 1 10 11 20 21 30 31 40 41 50 5 25 10 35 15 45 2 49 7 7 18 22 24 37 33 50 3 14
Sample Output 4
875 41 39 42 51 45 171 270 397 809 1 10 90 146 52
Sample Input 5
1 1 B 1 1
Sample Output 5
1