题目描述
译自 JOI 2023 Final T5「現代的な機械 / Modern Machine」
Bitaro 生日这天收到了一个 JOI 机作为生日礼物。JOI 机由一个球,N 条光带和 M 个按钮组成。光带从 1 到 N 编号。当 Bitaro 打开开关时,光带 i (1≤i≤N) 会发出颜色 Ci 的光(蓝光 (B) 或红光 (R))。按钮从 1 到 M 编号。如果 Bitaro 按下按钮 j (1≤j≤M),将发生如下事情。
- 把球放置在光带 Aj 上。
- 光带 Aj 变成红色(不管它原来是什么颜色)
- 进行如下操作,直到球被移除。
令 p 为球目前所在的光带编号。
- 如果光带 p 是蓝色,
光带 p 变为红色。在此之后,如果 p=1,这个球就被移除。否则,球移向光带 p−1。
- 如果光带 p 是红色,
光带 p 变为蓝色。在此之后,如果 p=N,这个球就被移除。否则,球移向光带 p+1。
Bitaro 对 JOI 机十分感兴趣。他计划进行 Q 次实验。在第 k (1≤k≤Q) 次实验中,在 Bitaro 开启电源后,他将按 Lk,Lk+1,…Rk 的顺序按下这些开关。在 Bitaro 按下一个开关后,他将等到球被移除后再按下下一个开关。
给定 JOI 机和实验的情况,写一个程序计算对于每个实验,当实验结束后红色的光带有多少。
注:每次实验之间互相独立。
输入格式
第一行两个整数 N,M。
第二行一个长度为 N 的字符串 C,字符串中仅包含字符 R 和 B。
第三行 M 个整数 Aj。
第四行一个整数 Q。
接下来 Q 行,每行两个整数 Lk,Rk。
输出格式
输出 Q 行,第 k (1≤k≤Q) 行输出一个整数,表示当第 k 个实验结束后红色的光带有多少。
数据范围与提示
对于全部数据,满足
- 3≤N≤1.2×105
- 1≤M≤1.2×105
- Ci (1≤i≤N) 不是 B 就是 R
- 1≤Aj≤N (1≤j≤M)
- 1≤Q≤1.2×105
- 1≤Lk≤Rk≤M (1≤k≤Q)
详细子任务附加限制及分值如下表。
子任务编号 |
附加限制 |
分值 |
1 |
N≤300,M≤300,Q≤1 |
3 |
2 |
N≤7 000,M≤7 000,Q=1 |
12 |
3 |
Q≤5 |
10 |
4 |
N=10 且 Ci (1≤i≤N) 是 R |
11 |
5 |
存在一个整数 t (0≤t≤N),使得对于每个 i≤t 都有 Ci 是 R,对于每个 i>t 都有 Ci 是 B |
26 |
6 |
Aj≤20 或 Aj>N−20 (1≤j≤M) |
17 |
7 |
无附加限制 |
21 |