Ela Takes Dancing Class

题目描述

DTL engineers love partying in the weekend. Ela does, too! Unfortunately, she didn't know how to dance yet. Therefore, she decided to take a dancing class.There are $ n $ students in the dancing class, including Ela. In the final project, $ n $ students will participate in a choreography described below. $ n $ students are positioned on the positive side of the $ Ox $ -axis. The $ i $ -th dancer is located at $ a_i > 0 $ . Some dancers will change positions during the dance (we'll call them movable dancers), and others will stay in the same place during a choreography (we'll call them immovable dancers). We distinguish the dancers using a binary string $ s $ of length $ n $ : if $ s_i $ equals '1', then the $ i $ -th dancer is movable, otherwise the $ i $ -th dancer is immovable. Let's call the "positive energy value" of the choreography $ d > 0 $ . The dancers will perform "movements" based on this value. Each minute after the dance begins, the movable dancer with the smallest $ x $ -coordinate will start moving to the right and initiate a "movement". At the beginning of the movement, the dancer's energy level will be initiated equally to the positive energy value of the choreography, which is $ d $ . Each time they move from some $ y $ to $ y+1 $ , the energy level will be decreased by $ 1 $ . At some point, the dancer might meet other fellow dancers in the same coordinates. If it happens, then the energy level of the dancer will be increased by $ 1 $ . A dancer will stop moving to the right when his energy level reaches $ 0 $ , and he doesn't share a position with another dancer. The dancers are very well-trained, and each "movement" will end before the next minute begins. To show her understanding of this choreography, Ela has to answer $ q $ queries, each consisting of two integers $ k $ and $ m $ . The answer to this query is the coordinate of the $ m $ -th dancer of both types from the left at $ k $ -th minute after the choreography begins. In other words, denote $ x_{k, 1}, x_{k, 2}, \dots, x_{k, n} $ as the sorted coordinates of the dancers at $ k $ -th minute from the beginning, you need to print $ x_{k, m} $ .

输入输出格式

输入格式

The first line contains three integers $ n $ , $ d $ and $ q $ ( $ 1 \le n \le 10^5 $ ; $ 1 \le d \le 10^9 $ ; $ 1 \le q \le 10^5 $ ) — the number of dancers, the positive energy value of the choreography, and the number of queries. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_1 < a_2 < \dots < a_n \le 10^9 $ ) — the coordinates of each dancer. The third line contains a binary string $ s $ of length $ n $ — the movability of each dancer. Each character is either '0' or '1'. It is guaranteed that $ s $ contains at least one character '1'. Then $ q $ lines follow, the $ i $ -th of them contains two integers $ k_i $ and $ m_i $ ( $ 1 \le k_i \le 10^9 $ , $ 1 \le m_i \le n $ ) — the content of each query.

输出格式

Output $ q $ lines, each contains a single integer — the answer for the corresponding query.

输入输出样例

输入样例 #1

4 3 8
1 3 6 7
1011
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4

输出样例 #1

3
5
6
7
3
6
7
10

输入样例 #2

1 1 5
2
1
1 1
2 1
3 1
4 1
5 1

输出样例 #2

3
4
5
6
7

说明

Let's consider the first example test case. In the first minute, $ 1 $ is the lowest coordinate between movable dancers. The energy level is initiated with $ 3 $ . Then the following happens: - The dancer moves from $ 1 $ to $ 2 $ . The energy level decreased to $ 2 $ . - The dancer moves from $ 2 $ to $ 3 $ . The energy level decreased to $ 1 $ , then increased to $ 2 $ when she met another dancer at $ 3 $ . - The dancer moves from $ 3 $ to $ 4 $ . The energy level decreased to $ 1 $ . - The dancer moves from $ 4 $ to $ 5 $ . The energy level decreased to $ 0 $ . At the end of the first minute, the sorted coordinates of the dancers become $ [3, 5, 6, 7] $ , and their respective movability is '0111'. In the second minute, $ 5 $ is the lowest coordinate between movable dancers. The energy level is initiated with $ 3 $ . Then the following happens: - The dancer moves from $ 5 $ to $ 6 $ . The energy level decreased to $ 2 $ , then increased to $ 3 $ when she met another dancer at $ 6 $ . - The dancer moves from $ 6 $ to $ 7 $ . The energy level decreased to $ 2 $ , then increased to $ 3 $ when she met another dancer at $ 7 $ . - The dancer moves from $ 7 $ to $ 8 $ . The energy level decreased to $ 2 $ . - The dancer moves from $ 8 $ to $ 9 $ . The energy level decreased to $ 1 $ . - The dancer moves from $ 9 $ to $ 10 $ . The energy level decreased to $ 0 $ . At the end of the second minute, the sorted coordinates of the dancers become $ [3, 6, 7, 10] $ , and their respective movability is '0111'.

**Ela参加舞蹈课**

**题目描述：**
Ela参加了一个有n个学生的舞蹈班，包括她在内。在最后的舞蹈编排中，n个学生将参与下面的舞蹈。

n个学生位于x轴的正半轴上。第i个舞者的位置是$a_i > 0$。一些舞者在舞蹈过程中会改变位置（我们称它们为可移动舞者），而其他舞者将在整个舞蹈过程中保持原地（我们称它们为不可移动舞者）。我们用一个长度为n的二进制字符串s来区分舞者：如果$s_i$等于'1'，那么第i个舞者是可移动的，否则第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$行，第$i$行包含两个整数$k_i$和$m_i$（$1 \le k_i \le 10^9$，$1 \le m_i \le n$）——每个查询的内容。

**输出格式：**
输出$q$行，每行包含一个整数——对应查询的答案。

**输入输出样例：**

**输入样例 #1：**
```
4 3 8
1 3 6 7
1011
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
```

**输出样例 #1：**
```
3
5
6
7
3
6
7
10
```

**输入样例 #2：**
```
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1
```

**输出样例 #2：**
```
3
4
5
6
7
```

**说明：**
考虑第一个示例测试用例。

在第一分钟，1是可移动舞者之间最小的坐标。能量值初始化为3。然后发生以下情况：

- 舞者从1移动到2。能量值减少到2。
- 舞者从2移动到3。能量值减少到1，然后在遇到另一个舞者在3时增加到2。
- 舞者从3移动到4。能量值减少到1。
- 舞者从4移动到5。能量值减少到0。

在第一分钟结束时，舞者的排序坐标变为[3, 5, 6, 7]，它们各自的可移动性为'0111'。

在第二分钟，5是可移动舞者之间最小的坐标。能量值初始化为3。然后发生以下情况：

- 舞者从5移动到6。能量值减少到2，然后在遇到另一个舞者在6时增加到3。
- 舞者从6移动到7。能量值减少到**Ela参加舞蹈课** **题目描述：** Ela参加了一个有n个学生的舞蹈班，包括她在内。在最后的舞蹈编排中，n个学生将参与下面的舞蹈。 n个学生位于x轴的正半轴上。第i个舞者的位置是$a_i > 0$。一些舞者在舞蹈过程中会改变位置（我们称它们为可移动舞者），而其他舞者将在整个舞蹈过程中保持原地（我们称它们为不可移动舞者）。我们用一个长度为n的二进制字符串s来区分舞者：如果$s_i$等于'1'，那么第i个舞者是可移动的，否则第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$行，第$i$行包含两个整数$k_i$和$m_i$（$1 \le k_i \le 10^9$，$1 \le m_i \le n$）——每个查询的内容。 **输出格式：** 输出$q$行，每行包含一个整数——对应查询的答案。 **输入输出样例：** **输入样例 #1：** ``` 4 3 8 1 3 6 7 1011 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 ``` **输出样例 #1：** ``` 3 5 6 7 3 6 7 10 ``` **输入样例 #2：** ``` 1 1 5 2 1 1 1 2 1 3 1 4 1 5 1 ``` **输出样例 #2：** ``` 3 4 5 6 7 ``` **说明：** 考虑第一个示例测试用例。 在第一分钟，1是可移动舞者之间最小的坐标。能量值初始化为3。然后发生以下情况： - 舞者从1移动到2。能量值减少到2。 - 舞者从2移动到3。能量值减少到1，然后在遇到另一个舞者在3时增加到2。 - 舞者从3移动到4。能量值减少到1。 - 舞者从4移动到5。能量值减少到0。 在第一分钟结束时，舞者的排序坐标变为[3, 5, 6, 7]，它们各自的可移动性为'0111'。 在第二分钟，5是可移动舞者之间最小的坐标。能量值初始化为3。然后发生以下情况： - 舞者从5移动到6。能量值减少到2，然后在遇到另一个舞者在6时增加到3。 - 舞者从6移动到7。能量值减少到