CF2150A.Incremental Path

Rymdkraft - Rymdsylt

⠀

本题不允许使用 Hack。

有一条包含 $10^9$ 个格子的带子，这些格子按 $1$ 到 $10^9$ 编号。每个格子可以是黑色或白色。起初，有 $m$ 个不同的格子 $a_1, a_2, \ldots, a_m$ 是黑色，其余的都是白色。

如果有人当前位于格子 $x$，他可能会被给出以下两种指令之一：

• $\texttt{A}$：跳到下一个格子，即格子 $x+1$；
• $\texttt{B}$：跳到下一个白色格子，即最小的 $y > x$，满足格子 $y$ 是白色。

有一串长度为 $n$ 的命令字符串 $s$，包含 $n$ 个指令。对于每一个 $i$ 从 $1$ 到 $n$，一名"参与者"进行如下操作：

• 从格子 $1$ 出发；
• 按顺序执行 $s$ 的前 $i$ 个命令；
• 将最后到达的格子涂黑（如果本来已经是黑色，则保持不变）。

你需要回答，最终哪些格子是黑色的，并按升序输出这些格子的编号。

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。随后每组测试用例如下：

每个测试用例第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 10^5$），分别表示命令数量和初始黑色格子的数量。

第二行是一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{A}$ 和 $\texttt{B}$ 组成，表示命令序列。

第三行包含 $m$ 个正整数 $a_1, a_2, \ldots, a_m$（$1 \leq a_1 < a_2 < \ldots < a_m \leq 10^9$），表示初始为黑色的格子的编号。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和不超过 $10^5$。

对于每个测试用例，输出两行：

• 第一行输出一个整数 $k$，表示最后黑色格子的数量；
• 第二行输出这 $k$ 个黑色格子的编号，升序排列。

在第一个测试用例中，最初黑色格子为 $2$ 和 $5$。

第 $1$ 位参与者：

• 从 $1$ 号格子出发；
• 执行命令 $\texttt{B}$，跳到下一个白色格子（$3$）；
• 将 $3$ 号格子涂黑。

第 $2$ 位参与者：

• 从 $1$ 号格子出发；
• 执行命令 $\texttt{B}$，跳到下一个白色格子（$4$）；
• 执行命令 $\texttt{A}$，跳到下一个格子（$5$）；
• 将 $5$ 号格子涂黑（已经是黑色，保持不变）。

第 $3$ 位参与者：

• 从 $1$ 号格子出发；
• 执行命令 $\texttt{B}$，跳到下一个白色格子（$4$）；
• 执行命令 $\texttt{A}$，跳到下一个格子（$5$）；
• 执行命令 $\texttt{B}$，跳到下一个白色格子（$6$）；
• 将 $6$ 号格子涂黑。

最后黑色格子为 $\{2, 3, 5, 6\}$。

在第二个测试用例中，三位参与者最终分别停在 $2$、$3$、$6$ 号格子。

由 ChatGPT 5 翻译