P9353 [JOI 2023 Final] 现代机器 / Modern Machine

Bitaro 收到了一个 JOI 机器作为生日礼物。 JOI 机器由一个球、$N$ 个灯光瓷砖和 $M$ 个按钮组成。灯光瓷砖从 $1$ 到 $N$ 编号。当 Bitaro 打开电源时，灯光瓷砖 $i$ ($1 \leq i \leq N$) 会发出颜色为 $C_i$（蓝色（$\texttt B$）或红色（$\texttt R$））的光。按钮从 $1$ 到 $M$ 编号。 如果 Bitaro 按下按钮 $j$ ($1 \leq j \leq 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 \leq k \leq Q$），在 Bitaro 打开电源后，Bitaro 按顺序按下按钮 $L_k, L_{k} + 1, \dots , R_k$。在 Bitaro 按下一个按钮后，他不会按下下一个按钮，并等待球被移除。 给定 JOI 机器的信息和实验，编写一个程序来计算每次实验结束时颜色为红色的灯光瓷砖的数量。

从标准输入读取以下数据。 > $N$ $M$ > $C_1\ C_2 \dots C_N$ > $A_1\ A_2 \dots A_M$ > $Q$ > $L_1\ R_1$ > $L_2\ R_2$ > $\dots$ > $L_Q\ R_Q$

向标准输出写入 $Q$ 行。在第 $k$ 行（$1 \leq k \leq Q$），输出应包含第 $k$ 次实验结束时颜色为红色的灯光瓷砖的数量。

**【样例解释 #1】** 第一次实验如下进行。 1. Bitaro 按下按钮 1，球被放置在灯光瓷砖 4 上。 2. 灯光瓷砖 4 变为红色。由于灯光瓷砖 4 的原始颜色是红色，灯光瓷砖 4 的颜色没有改变。 3. 之后，执行以下操作。 （1）由于灯光瓷砖 4 的当前颜色是红色，灯光瓷砖 4 变为蓝色，球移动到灯光瓷砖 5。 （2）由于灯光瓷砖 5 的当前颜色是蓝色，灯光瓷砖 5 变为红色，球移动到灯光瓷砖 4。 （3）由于灯光瓷砖 4 的当前颜色是蓝色，灯光瓷砖 4 变为红色，球移动到灯光瓷砖 3。 （4）由于灯光瓷砖 3 的当前颜色是红色，灯光瓷砖 3 变为蓝色，球移动到灯光瓷砖 4。 （5）由于灯光瓷砖 4 的当前颜色是红色，灯光瓷砖 4 的颜色变为蓝色，球移动到灯光瓷砖 5。 （6）由于灯光瓷砖 5 的当前颜色是红色，灯光瓷砖 5 的颜色变为蓝色，球被移除。 实验结束后，灯光瓷砖 1 是唯一一个当前颜色为红色的灯光瓷砖。因此，输出 1。 本样例满足子任务 1,2,3,6,7 的限制。 **【样例解释 #2】** 对于第一次实验，灯光瓷砖 1, 2, 3, 4, 5 是实验结束后当前颜色为红色的灯光瓷砖。由于有五个这样的灯光瓷砖，输出 5。 对于第二次实验，没有灯光瓷砖在实验结束后颜色为红色。因此，输出 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 1.2 \times 10^5$； - $1 \leq M \leq 1.2 \times 10^5$； - $C_i \in \{\texttt{B},\texttt{R}\}$； - $1 \leq A_j \leq N$； - $1 \leq Q \leq 1.2 \times 10^5$； - $1 \leq L_k \leq R_k \leq M$； - $N, M, A_j, Q, L_k, R_k$ 均为整数。 **【子任务】** **本题采用捆绑测试**。 1. (3 分) $N,M \leq 300$，$Q = 1$。 2. (12 分) $N, M \leq 7000$，$Q = 1$。 3. (10 分) $Q \leq 5$。 4. (11 分) $N = 10$，$C_i = \texttt R$。 5. (26 分) 存在一个整数 $t \in [0, N]$，满足对 $1 \leq i \leq t$，$C_i = \texttt R$；且对 $t < i \leq N$，$C_i = \texttt B$。 6. (17 分) $A_j \leq 20$ 或 $A_j > N - 20$。 7. (21 分) 无特殊约定。 题面翻译由 ChatGPT-4o 提供。