分数: 466 分
问题陈述
高桥已安排 N 白色和黑色的石头排成一排。
的颜色 i左边的第一个石头由 i- 字符串的第一个字符 S,其中 W 对应于白色石头并且 B 对应于黑色石头。
连续间隔 [l, r] (1 \leq l \leq r \leq N) 指的是从 l-第 r从左边算起。
考虑取出连续间隔中的所有石头,然后按照您喜欢的任何顺序将它们重新排列成一行。如果存在一种排列方式,使得每两个相邻的棋子都有不同的颜色,我们称该连续间隔为 良好的间隔.
特别是,长度连续的间隔 1 始终是一个很好的间隔。
青木问 Q 问题。
在 i第题,整数 L_i, R_i 。
对于每个问题,找出连续区间中良好区间的数量 [l, r] 满意 L_i \leq l \leq r \leq R_i.
约束
- 1 \leq N \leq 5 \times 10^4
- 1 \leq Q \leq 5 \times 10^4
- S 是一个长度为 N 仅包含
W和B - 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
第一行包含石子数量 N 和问题数量 Q,用空格分隔。
第二行包含一个字符串 S 长度 N 代表每颗宝石的颜色。
的 i- 以下各项 Q 行包含整数 L_i, R_i 代表 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