CF1737G Ela Takes Dancing Class

DTL 的工程师们喜欢在周末开派对，Ela 也不例外！可惜她还不会跳舞，因此她决定去上舞蹈课。舞蹈班里有 $n$ 名学生，包括 Ela。在期末项目中，$n$ 名学生将参与如下编排的舞蹈。 $n$ 名学生站在 $Ox$ 轴的正半轴上。第 $i$ 位舞者的位置为 $a_i > 0$。在舞蹈过程中，有些舞者会移动（称为可移动舞者），有些则会保持原地不动（称为不可移动舞者）。我们用一个长度为 $n$ 的二进制字符串 $s$ 来区分舞者：如果 $s_i$ 等于 '1'，则第 $i$ 位舞者是可移动的，否则为不可移动的。 我们将编舞的“正能量值”记为 $d > 0$。舞者们将根据该值进行“移动”。 每过一分钟，所有可移动舞者中 $x$ 坐标最小的那一位会开始向右移动并发起一次“移动”。在移动开始时，该舞者的能量值初始化为编舞的正能量值 $d$。每当她从某个 $y$ 移动到 $y+1$ 时，能量值减少 $1$。如果她在某一时刻与其他舞者相遇（即处于同一坐标），她的能量值会增加 $1$。当舞者的能量值降为 $0$ 且此时没有与其他舞者处于同一位置时，她会停止向右移动。 这些舞者训练有素，每次“移动”都会在下一分钟开始前结束。 为了展示她对编舞的理解，Ela 需要回答 $q$ 个询问，每个询问包含两个整数 $k$ 和 $m$。对于每个询问，要求输出编舞开始后第 $k$ 分钟时，从左到右第 $m$ 位舞者的坐标。换句话说，记 $x_{k,1}, x_{k,2}, \dots, x_{k,n}$ 为第 $k$ 分钟时所有舞者的有序坐标，你需要输出 $x_{k,m}$。

第一行包含三个整数 $n$、$d$ 和 $q$（$1 \le n \le 10^5$，$1 \le d \le 10^9$，$1 \le q \le 10^5$），分别表示舞者人数、编舞的正能量值和询问数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 < a_2 < \dots < a_n \le 10^9$），表示每位舞者的初始坐标。 第三行包含一个长度为 $n$ 的二进制字符串 $s$，表示每位舞者是否可移动。每个字符为 '0' 或 '1'。保证 $s$ 至少包含一个 '1'。 接下来 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$（$1 \le k_i \le 10^9$，$1 \le m_i \le n$），表示每个询问的内容。

输出 $q$ 行，每行一个整数，表示对应询问的答案。

我们来看第一个样例测试。 在第一分钟，$1$ 是所有可移动舞者中最小的坐标。能量值初始化为 $3$。然后发生如下过程： - 舞者从 $1$ 移动到 $2$，能量值减少到 $2$。 - 舞者从 $2$ 移动到 $3$，能量值减少到 $1$，遇到另一位舞者，能量值增加到 $2$。 - 舞者从 $3$ 移动到 $4$，能量值减少到 $1$。 - 舞者从 $4$ 移动到 $5$，能量值减少到 $0$。 第一分钟结束后，舞者的有序坐标变为 $[3, 5, 6, 7]$，对应的可移动性为 '0111'。 在第二分钟，$5$ 是所有可移动舞者中最小的坐标。能量值初始化为 $3$。然后发生如下过程： - 舞者从 $5$ 移动到 $6$，能量值减少到 $2$，遇到另一位舞者，能量值增加到 $3$。 - 舞者从 $6$ 移动到 $7$，能量值减少到 $2$，遇到另一位舞者，能量值增加到 $3$。 - 舞者从 $7$ 移动到 $8$，能量值减少到 $2$。 - 舞者从 $8$ 移动到 $9$，能量值减少到 $1$。 - 舞者从 $9$ 移动到 $10$，能量值减少到 $0$。 第二分钟结束后，舞者的有序坐标变为 $[3, 6, 7, 10]$，对应的可移动性为 '0111'。 由 ChatGPT 4.1 翻译