CF2187E Doors and Keys

有 $n+1$ 个房间排成一排，从左到右编号为 $1$ 到 $n+1$。还有 $n$ 扇门，编号为 $1$ 到 $n$，第 $i$ 扇门连接房间 $i$ 和房间 $i+1$。每扇门 $i$ 关联一个非负整数 $a_i$。 你会得到一个长度为 $n$ 的二进制字符串 $s$（只包含 $0$ 或 $1$）。对于每个 $1 \le i \le n$： - 如果 $s_i=1$，则房间 $i$ 初始时有一把钥匙。 - 否则，房间 $i$ 没有钥匙。 在第 $0$ 秒开始时，你在房间 $1$，所有门都是关闭的。对于每个 $k \ge 0$，在第 $k$ 秒内会依次发生以下事件： - 在第 $k$ 秒的开始时，所有 $a_j=k$ 的门 $j$ 会自动打开。 - 假设你当前在房间 $i$： - 如果你没有携带钥匙，且房间 $i$ 里至少有一把钥匙，你可以捡起一把钥匙并带在身上。 - 如果你身上有钥匙，可以在房间 $i$ 丢下钥匙。 - 在第 $k$ 秒的末尾： - 你可以向右走到房间 $i+1$。如果门 $i$ 还未打开，必须携带钥匙才能通过，使用后该钥匙消耗，门也会随之打开。 - 如果 $i>1$，你也可以向左走到房间 $i-1$。 - 或者你可以停留在原房间 $i$。 任意一扇门，不论是自动打开还是用钥匙打开，一旦打开便永久保持开启。 你随时最多只能携带一把钥匙。虽然初始时每个房间最多只有一把钥匙，但在过程中，可能会有多个钥匙被放置在同一个房间。 对于每个 $1 \le i \le n$，请你求出从房间 $1$ 到达房间 $i+1$ 所需要的最小秒数。注意，每个 $i$ 的答案互不相关。 $^*$ 二进制字符串是指只包含 $0$ 或 $1$ 的字符串。

每组测试数据包含多组用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。接下来的每组用例描述如下： 每组用例的第一行为一个整数 $n$（$1 \le n \le 2 \times 10^5$）——门的数量。 第二行有 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \le a_i \le 2 \times 10^5$）——每扇门对应的整数。 第三行为一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示到达房间 $i+1$ 所需的最小秒数。

在第一个测试用例中，第 $1$ 扇门会在第 $0$ 秒开始时打开。你可以在第 $0$ 秒末移动到房间 $2$，因此在第 $1$ 秒到达房间 $2$。 在第二个测试用例中，第 $1$ 扇门会在第 $2$ 秒开始时自动打开。你必须在房间 $1$ 等待，直到在第 $2$ 秒末移动到房间 $2$，因此在第 $3$ 秒到达房间 $2$。 在第三个测试用例中，你可以在房间 $1$ 拿起钥匙，并在第 $0$ 秒末用钥匙打开门 $1$，这样在第 $1$ 秒到达房间 $2$。 由 ChatGPT 5 翻译