AT_joi2023ho_e 現代的な機械 (Modern Machine)

比太郎作为生日礼物收到了 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$）时，会发生如下事件： 1. 球被放在编号为 $A_j$ 的发光瓷砖上。 2. 编号为 $A_j$ 的发光瓷砖的颜色会（无论原本颜色如何）变为红色。 3. 在球被拿走之前，将不断重复以下操作： 设球当前所在的发光瓷砖编号为 $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.（$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. 按下第 $1$ 个按钮，将球放在瓷砖 $4$ 上。 2. 瓷砖 $4$ 的颜色变为红色。由于原本也是红色，颜色不变。 3. 随后发生如下事件： 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 翻译