#3944. 「JOI 2023 Final」现代机器

传统 $2500$ ms $1024$ MiB

$41$ 通过
$176$ 提交

题目描述

译自 JOI $2023$ Final T5「現代的な機械 / Modern Machine」

Bitaro 生日这天收到了一个 JOI 机作为生日礼物。JOI 机由一个球，$N$ 条光带和 $M$ 个按钮组成。光带从 $1$ 到 $N$ 编号。当 Bitaro 打开开关时，光带 $i$ $(1\le i\le N)$ 会发出颜色 $C_i$ 的光（蓝光 (B) 或红光 (R)）。按钮从 $1$ 到 $M$ 编号。如果 Bitaro 按下按钮 $j$ $(1\le j\le M)$，将发生如下事情。

1. 把球放置在光带 $A_j$ 上。
2. 光带 $A_j$ 变成红色（不管它原来是什么颜色）
3. 进行如下操作，直到球被移除：
   • 令 $p$ 为球目前所在的光带编号。
   • 如果光带 $p$ 是蓝色：
     • 光带 $p$ 变为红色。
     • 在此之后，如果 $p=1$，这个球就被移除。否则，球移向光带 $p-1$。
   • 如果光带 $p$ 是红色：
     • 光带 $p$ 变为蓝色。
     • 在此之后，如果 $p=N$，这个球就被移除。否则，球移向光带 $p+1$。

Bitaro 对 JOI 机十分感兴趣。他计划进行 $Q$ 次实验。在第 $k$ $(1\le k\le Q)$ 次实验中，在 Bitaro 开启电源后，他将按 $L_k,L_k+1,\ldots R_k$ 的顺序按下这些开关。在 Bitaro 按下一个开关后，他将等到球被移除后再按下下一个开关。

给定 JOI 机和实验的情况，写一个程序计算对于每个实验，当实验结束后红色的光带有多少。

注：每次实验之间互相独立。

输入格式

第一行两个整数 $N,M$。

第二行一个长度为 $N$ 的字符串 $C$，字符串中仅包含字符 R 和 B。

第三行 $M$ 个整数 $A_j$。

第四行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $L_k,R_k$。

输出格式

输出 $Q$ 行，第 $k$ $(1\le k\le Q)$ 行输出一个整数，表示当第 $k$ 个实验结束后红色的光带有多少。

样例 1

输入

5 1
RBRRB
4
1
1 1

输出

1

第一个实验按如下进行。

1. Bitaro 按下按钮 $1$，然后球被放在光带 $4$ 上。
2. 光带 $4$ 变红。因为光带 $4$ 本身就是红色的，所以颜色不变。
3. 在此之后，进行了如下操作：
   • 因为目前光带 $4$ 是红色的，所以光带 $4$ 变蓝，然后球移动到光带 $5$ 上。
   • 因为目前光带 $5$ 是蓝色的，所以光带 $5$ 变红，然后球移动到光带 $4$ 上。
   • 因为目前光带 $4$ 是蓝色的，所以光带 $4$ 变红，然后球移动到光带 $3$ 上。
   • 因为目前光带 $3$ 是红色的，所以光带 $3$ 变蓝，然后球移动到光带 $4$ 上。
   • 因为目前光带 $4$ 是红色的，所以光带 $4$ 变蓝，然后球移动到光带 $5$ 上。
   • 因为目前光带 $5$ 是红色的，所以光带 $5$ 变蓝，然后球被移除。

在实验后，光带 $1$ 是唯一红色的光带。所以输出 $1$。

这组样例满足子任务 $1,2,3,6,7$ 的限制。

样例 2

输入

5 3
RBRBR
1 3 4
2
2 3
1 3

输出

5
0

对于第一个实验，在结束后光带 $1,2,3,4,5$ 都是红色的，所以输出 $5$。

对于第二个实验，在结束后没有光带是红色的，所以输出 $0$。

这组样例满足子任务 $3,6,7$ 的限制。

样例 3

输入

10 3
BBRRBRBRRB
2 10 5
1
1 3

输出

2

这组样例满足子任务 $1,2,3,6,7$ 的限制。

样例 4

输入

10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10

输出

4
8
10
0
9

这组样例满足子任务 $3,4,5,6,7$ 的限制。

样例 5

输入

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

输出

2
6
0
10
7

这组样例满足子任务 $3,5,6,7$ 的限制。

样例 6

输入

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

输出

21
15
15
4
17
16
14
20
12
23

这组样例满足子任务 $6,7$ 的限制。

数据范围与提示

对于全部数据，满足

• $3\le N\le 1.2\times 10^5$
• $1\le M\le 1.2\times 10^5$
• $C_i$ $(1\le i\le N)$ 不是 B 就是 R
• $1\le A_j\le N$ $(1\le j\le M)$
• $1\le Q\le 1.2\times 10^5$
• $1\le L_k\le R_k\le M$ $(1\le k\le Q)$

详细子任务附加限制及分值如下表。

子任务编号	附加限制	分值
1	$N\le 300,M\le 300,Q=1$	$3$
2	$N\le 7\,000,M\le 7\,000,Q=1$	$12$
3	$Q\le 5$	$10$
4	$N=10$ 且 $C_i$ $(1\le i\le N)$ 是 R	$11$
5	存在一个整数 $t$ $(0\le t\le N)$，使得对于每个 $i\le t$ 都有 $C_i$ 是 R，对于每个 $i>t$ 都有 $C_i$ 是 B	$26$
6	$A_j\le 20$ 或 $A_j>N-20$ $(1\le j\le M)$	$17$
7	无附加限制	$21$