← 返回题目列表

AtCoder · awc0088_e

E. 可以交替安排的间隔

中文机器翻译题面 查看原题

分数: 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