AT_joi2023ho_e.現代的な機械 (Modern Machine)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

比太郎作为生日礼物收到了 JOI 机器。JOI 机器由 $1$ 个球、 $N$ 个发光瓷砖和 $M$ 个按钮组成。每个发光瓷砖编号为 $1$ 到 $N$ ，通电后，编号为 $i$ （ $1 \leq i \leq N$ ）的瓷砖会以颜色 $C_i$ （可以为蓝色（B）或红色（R））亮起。另外，每个按钮编号为 $1$ 到 $M$ ，按下第 $j$ 个按钮（ $1 \leq j \leq M$ ）时，会发生如下事件：

球被放在编号为 $A_j$ 的发光瓷砖上。
编号为 $A_j$ 的发光瓷砖的颜色会（无论原本颜色如何）变为红色。
在球被拿走之前，将不断重复以下操作：

设球当前所在的发光瓷砖编号为 $p$ 。
- 如果瓷砖 $p$ 的颜色为蓝色，则将其变为红色。随后，如果 $p=1$ ，则球被拿走；否则，球移动到瓷砖 $p-1$ 上。
- 如果瓷砖 $p$ 的颜色为红色，则将其变为蓝色。随后，如果 $p=N$ ，则球被拿走；否则，球移动到瓷砖 $p+1$ 上。

比太郎对 JOI 机器产生了兴趣，准备进行 $Q$ 次实验。第 $k$ 次（ $1 \leq k \leq Q$ ）实验的内容是：在打开机器之后，按顺序按下按钮 $L_k, L_k+1, \ldots, R_k$ 。不过，在球被拿走之前，需要等待，不执行下一个按钮的操作。

给定 JOI 机器的相关信息和实验安排，请编写程序，对于每次实验，输出在实验结束后状态下，颜色为红色的发光瓷砖数量。

输入格式

输入按如下格式从标准输入给出：

$N$ $M$
$C_1C_2\cdots C_N$
$A_1$ $A_2$ $\cdots$ $A_M$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

输出格式

请输出 $Q$ 行，第 $k$ 行为第 $k$ 次实验结束后，颜色为红色的发光瓷砖的数量。

输入输出样例

输入#1
```
5 1
RBRRB
4
1
1 1
```
输出#1
```
1
```
输入#2
```
5 3
RBRBR
1 3 4
2
2 3
1 3
```
输出#2
```
5
0
```
输入#3
```
10 3
BBRRBRBRRB
2 10 5
1
1 3
```
输出#3
```
2
```

输入#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

输入#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

输出#5

输入#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

输出#6

说明/提示

小子任务

1.（ $3$ 分） $N \leq 300$ ， $M \leq 300$ ， $Q=1$ 。
2.（ $12$ 分） $N \leq 7000$ ， $M \leq 7000$ ， $Q=1$ 。
3.（ $10$ 分） $Q \leq 5$ 。
4.（ $11$ 分） $N=10$ ，所有 $C_i$ （ $1 \leq i \leq N$ ）均为 R。
5.（ $26$ 分）存在整数 $t$ （ $0 \leq t \leq N$ ），当 $i \leq t$ 时 $C_i$ 为 R，当 $i > t$ 时 $C_i$ 为 B。
6.（ $17$ 分）对于任意 $1 \leq j \leq M$ ， $A_j \leq 20$ 或 $A_j > N - 20$ 。
7.（ $21$ 分）无额外限制。

样例解释 1

第 $1$ 次实验的操作流程如下：

按下第 $1$ 个按钮，将球放在瓷砖 $4$ 上。
瓷砖 $4$ 的颜色变为红色。由于原本也是红色，颜色不变。
随后发生如下事件：
1. 当前瓷砖 $4$ 为红色，将其变为蓝色，球移到瓷砖 $5$ 。
2. 当前瓷砖 $5$ 为蓝色，将其变为红色，球移到瓷砖 $4$ 。
3. 当前瓷砖 $4$ 为蓝色，将其变为红色，球移到瓷砖 $3$ 。
4. 当前瓷砖 $3$ 为红色，将其变为蓝色，球移到瓷砖 $4$ 。
5. 当前瓷砖 $4$ 为红色，将其变为蓝色，球移到瓷砖 $5$ 。
6. 当前瓷砖 $5$ 为红色，将其变为蓝色，球被拿走。

实验结束时，只有瓷砖 $1$ 是红色，所以输出 $1$ 。

本输入满足小子任务 $1,2,3,6,7$ 的约束。

样例解释 2

第 $1$ 次实验结束时，瓷砖 $1,2,3,4,5$ 是红色，共有 $5$ 个，所以输出 $5$ 。

第 $2$ 次实验结束时，没有瓷砖是红色，输出 $0$ 。

本输入满足小子任务 $3,6,7$ 的约束。

样例解释 3

本输入满足小子任务 $1,2,3,6,7$ 的约束。

样例解释 4

本输入满足小子任务 $3,4,5,6,7$ 的约束。

样例解释 5

本输入满足小子任务 $3,5,6,7$ 的约束。

样例解释 6

本输入满足小子任务 $6,7$ 的约束。

约束条件

$3 \leq N \leq 120\,000$ 。
$1 \leq M \leq 120\,000$ 。
$C_i$ （ $1 \leq i \leq N$ ）是 B 或 R。
$1 \leq A_j \leq N$ （ $1 \leq j \leq M$ ）。
$1 \leq Q \leq 120\,000$ 。
$1 \leq L_k \leq R_k \leq M$ （ $1 \leq k \leq Q$ ）。
$N, M, A_j, Q, L_k, R_k$ 均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页