309719: CF1725D. Deducing Sortability
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Deducing Sortability
题意翻译
有一个数组 $A$，可以在上面进行任意次操作。每次操作选择一个位置，把它减去 $2^c$ 后再乘 2（其中 $c$ 是已经在这个位置上操作过的操作数）。如果可以将它变得单调上升，那么它就是一个好的数组。 现在需要构造长为 $n$ 的一个好的数组，使得 $\sum A_i$ 最小，在此基础上使得它的字典序最小，输出 $\sum A_i$，并 $q$ 次询问某个位置上的值，保证位置升序给出。 $n \le 10^9$，$q \le \min(n, 10^5)$题目描述
Let's say Pak Chanek has an array $ A $ consisting of $ N $ positive integers. Pak Chanek will do a number of operations. In each operation, Pak Chanek will do the following: 1. Choose an index $ p $ ( $ 1 \leq p \leq N $ ). 2. Let $ c $ be the number of operations that have been done on index $ p $ before this operation. 3. Decrease the value of $ A_p $ by $ 2^c $ . 4. Multiply the value of $ A_p $ by $ 2 $ . After each operation, all elements of $ A $ must be positive integers. An array $ A $ is said to be sortable if and only if Pak Chanek can do zero or more operations so that $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $ . Pak Chanek must find an array $ A $ that is sortable with length $ N $ such that $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ is the minimum possible. If there are more than one possibilities, Pak Chanek must choose the array that is lexicographically minimum among them. Pak Chanek must solve the following things: - Pak Chanek must print the value of $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ for that array. - $ Q $ questions will be given. For the $ i $ -th question, an integer $ P_i $ is given. Pak Chanek must print the value of $ A_{P_i} $ . Help Pak Chanek solve the problem. Note: an array $ B $ of size $ N $ is said to be lexicographically smaller than an array $ C $ that is also of size $ N $ if and only if there exists an index $ i $ such that $ B_i < C_i $ and for each $ j < i $ , $ B_j = C_j $ .输入输出格式
输入格式
The first line contains two integers $ N $ and $ Q $ ( $ 1 \leq N \leq 10^9 $ , $ 0 \leq Q \leq \min(N, 10^5) $ ) — the required length of array $ A $ and the number of questions. The $ i $ -th of the next $ Q $ lines contains a single integer $ P_i $ ( $ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $ ) — the index asked in the $ i $ -th question.
输出格式
Print $ Q+1 $ lines. The $ 1 $ -st line contains an integer representing $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ . For each $ 1 \leq i \leq Q $ , the $ (i+1) $ -th line contains an integer representing $ A_{P_i} $ .
输入输出样例
输入样例 #1
6 3
1
4
5输出样例 #1
17
1
3
4输入样例 #2
1 0输出样例 #2
1说明
In the first example, the array $ A $ obtained is $ [1, 2, 3, 3, 4, 4] $ . We can see that the array is sortable by doing the following operations: - Choose index $ 5 $ , then $ A = [1, 2, 3, 3, 6, 4] $ . - Choose index $ 6 $ , then $ A = [1, 2, 3, 3, 6, 6] $ . - Choose index $ 4 $ , then $ A = [1, 2, 3, 4, 6, 6] $ . - Choose index $ 6 $ , then $ A = [1, 2, 3, 4, 6, 8] $ .Input
题意翻译
有一个数组 $A$，可以在上面进行任意次操作。每次操作选择一个位置，把它减去 $2^c$ 后再乘 2（其中 $c$ 是已经在这个位置上操作过的操作数）。如果可以将它变得单调上升，那么它就是一个好的数组。 现在需要构造长为 $n$ 的一个好的数组，使得 $\sum A_i$ 最小，在此基础上使得它的字典序最小，输出 $\sum A_i$，并 $q$ 次询问某个位置上的值，保证位置升序给出。 $n \le 10^9$，$q \le \min(n, 10^5)$Output
**题意翻译**
给定一个数组 $ A $，可以通过以下操作使其变得单调递增：选择一个位置，将其值减去 $ 2^c $（其中 $ c $ 是之前在该位置上执行的操作次数），然后将结果乘以 2。若能通过一系列操作使得数组 $ A $ 单调递增，则称其为好的数组。现在需要构造一个长度为 $ n $ 的好的数组，使得数组元素之和 $ \sum A_i $ 最小，在此基础上使其字典序最小。输出 $ \sum A_i $，并根据 $ q $ 次询问输出对应位置的值，保证询问的位置是升序给出的。
其中 $ n \le 10^9 $，$ q \le \min(n, 10^5) $。
**题目描述**
Pak Chanek有一个由 $ N $ 个正整数组成的数组 $ A $。Pak Chanek将对数组进行一系列操作，每次操作如下：
1. 选择一个索引 $ p $（$ 1 \leq p \leq N $）。
2. 设 $ c $ 为在此操作之前在索引 $ p $ 上执行的操作次数。
3. 将 $ A_p $ 的值减去 $ 2^c $。
4. 将 $ A_p $ 的值乘以 2。
每次操作后，数组 $ A $ 的所有元素都必须是正整数。
若Pak Chanek可以通过零次或多次操作使得 $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $，则称数组 $ A $ 是可排序的。
Pak Chanek必须找到一个可排序的数组 $ A $，其长度为 $ N $，使得 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ 的值最小。如果有多个这样的数组，Pak Chanek必须选择其中字典序最小的数组。
Pak Chanek必须解决以下问题：
- 输出数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。
- 对于每个查询，输出对应位置 $ P_i $ 上的值 $ A_{P_i} $。
注意：若存在一个索引 $ i $，使得 $ B_i < C_i $ 且对于所有 $ j < i $ 都有 $ B_j = C_j $，则称大小为 $ N $ 的数组 $ B $ 在字典序上小于大小为 $ N $ 的数组 $ C $。
**输入输出格式**
**输入格式**
第一行包含两个整数 $ N $ 和 $ Q $（$ 1 \leq N \leq 10^9 $，$ 0 \leq Q \leq \min(N, 10^5) $）——数组 $ A $ 的必要长度和查询的数量。
接下来的 $ Q $ 行中，第 $ i $ 行包含一个整数 $ P_i $（$ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $）——第 $ i $ 个查询中的索引。
**输出格式**
输出 $ Q+1 $ 行。第一行包含一个整数，表示数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。对于每个 $ 1 \leq i \leq Q $，第 $ i+1 $ 行包含一个整数，表示 $ A_{P_i} $ 的值。
**输入输出样例**
**输入样例 #1**
```
6 3
1
4
5
```
**输出样例 #1**
```
17
1
3
4
```
**输入样例 #2**
```
1 0
```
**输出样例 #2**
```
1
```
**说明**
在第一个例子中，获得的数组 $ A $ 为 $ [1, 2, 3, 3, 4, 4] $。通过以下操作，我们可以看到数组是可排序的：
- 选择索引 $ 5 $，则 $ A = [1, 2, 3, 3, 6, 4] $。
- 选择索引 $ 6 $，则 $ A = [1, 2, 3, 3, 6, 6] $。
- 选择索引 $ 4 $，则 $ A = [1, 2, 3, 4, 6, 6] $。
- 选择索引 $ 6 $，则 $ A = [1, 2, 3, 4, 6, 8] $。**题意翻译** 给定一个数组 $ A $，可以通过以下操作使其变得单调递增：选择一个位置，将其值减去 $ 2^c $（其中 $ c $ 是之前在该位置上执行的操作次数），然后将结果乘以 2。若能通过一系列操作使得数组 $ A $ 单调递增，则称其为好的数组。现在需要构造一个长度为 $ n $ 的好的数组，使得数组元素之和 $ \sum A_i $ 最小，在此基础上使其字典序最小。输出 $ \sum A_i $，并根据 $ q $ 次询问输出对应位置的值，保证询问的位置是升序给出的。 其中 $ n \le 10^9 $，$ q \le \min(n, 10^5) $。 **题目描述** Pak Chanek有一个由 $ N $ 个正整数组成的数组 $ A $。Pak Chanek将对数组进行一系列操作，每次操作如下： 1. 选择一个索引 $ p $（$ 1 \leq p \leq N $）。 2. 设 $ c $ 为在此操作之前在索引 $ p $ 上执行的操作次数。 3. 将 $ A_p $ 的值减去 $ 2^c $。 4. 将 $ A_p $ 的值乘以 2。 每次操作后，数组 $ A $ 的所有元素都必须是正整数。 若Pak Chanek可以通过零次或多次操作使得 $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $，则称数组 $ A $ 是可排序的。 Pak Chanek必须找到一个可排序的数组 $ A $，其长度为 $ N $，使得 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ 的值最小。如果有多个这样的数组，Pak Chanek必须选择其中字典序最小的数组。 Pak Chanek必须解决以下问题： - 输出数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。 - 对于每个查询，输出对应位置 $ P_i $ 上的值 $ A_{P_i} $。 注意：若存在一个索引 $ i $，使得 $ B_i < C_i $ 且对于所有 $ j < i $ 都有 $ B_j = C_j $，则称大小为 $ N $ 的数组 $ B $ 在字典序上小于大小为 $ N $ 的数组 $ C $。 **输入输出格式** **输入格式** 第一行包含两个整数 $ N $ 和 $ Q $（$ 1 \leq N \leq 10^9 $，$ 0 \leq Q \leq \min(N, 10^5) $）——数组 $ A $ 的必要长度和查询的数量。 接下来的 $ Q $ 行中，第 $ i $ 行包含一个整数 $ P_i $（$ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $）——第 $ i $ 个查询中的索引。 **输出格式** 输出 $ Q+1 $ 行。第一行包含一个整数，表示数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。对于每个 $ 1 \leq i \leq Q $，第 $ i+1 $ 行包含一个整数，表示 $ A_{P_i} $ 的值。 **输入输出样例** **输入样例 #1** ``` 6 3 1 4 5 ``` **输出样例 #1** ``` 17 1 3 4 ``` **输入样例 #2** ``` 1 0 ``` **输出样例 #2** ``` 1 ``` **说明** 在第一个例子中，获得的数组 $ A $ 为 $ [1, 2, 3, 3, 4, 4] $。通过以下操作，我们可以看到数组是可排序的： - 选择索引 $ 5 $，则 $ A = [1, 2, 3, 3, 6, 4] $。 - 选择索引 $ 6 $，则 $ A = [1, 2, 3, 3, 6, 6] $。 - 选择索引 $ 4 $，则 $ A = [1, 2, 3, 4, 6, 6] $。 - 选择索引 $ 6 $，则 $ A = [1, 2, 3, 4, 6, 8] $。
给定一个数组 $ A $，可以通过以下操作使其变得单调递增：选择一个位置，将其值减去 $ 2^c $（其中 $ c $ 是之前在该位置上执行的操作次数），然后将结果乘以 2。若能通过一系列操作使得数组 $ A $ 单调递增，则称其为好的数组。现在需要构造一个长度为 $ n $ 的好的数组，使得数组元素之和 $ \sum A_i $ 最小，在此基础上使其字典序最小。输出 $ \sum A_i $，并根据 $ q $ 次询问输出对应位置的值，保证询问的位置是升序给出的。
其中 $ n \le 10^9 $，$ q \le \min(n, 10^5) $。
**题目描述**
Pak Chanek有一个由 $ N $ 个正整数组成的数组 $ A $。Pak Chanek将对数组进行一系列操作，每次操作如下：
1. 选择一个索引 $ p $（$ 1 \leq p \leq N $）。
2. 设 $ c $ 为在此操作之前在索引 $ p $ 上执行的操作次数。
3. 将 $ A_p $ 的值减去 $ 2^c $。
4. 将 $ A_p $ 的值乘以 2。
每次操作后，数组 $ A $ 的所有元素都必须是正整数。
若Pak Chanek可以通过零次或多次操作使得 $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $，则称数组 $ A $ 是可排序的。
Pak Chanek必须找到一个可排序的数组 $ A $，其长度为 $ N $，使得 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ 的值最小。如果有多个这样的数组，Pak Chanek必须选择其中字典序最小的数组。
Pak Chanek必须解决以下问题：
- 输出数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。
- 对于每个查询，输出对应位置 $ P_i $ 上的值 $ A_{P_i} $。
注意：若存在一个索引 $ i $，使得 $ B_i < C_i $ 且对于所有 $ j < i $ 都有 $ B_j = C_j $，则称大小为 $ N $ 的数组 $ B $ 在字典序上小于大小为 $ N $ 的数组 $ C $。
**输入输出格式**
**输入格式**
第一行包含两个整数 $ N $ 和 $ Q $（$ 1 \leq N \leq 10^9 $，$ 0 \leq Q \leq \min(N, 10^5) $）——数组 $ A $ 的必要长度和查询的数量。
接下来的 $ Q $ 行中，第 $ i $ 行包含一个整数 $ P_i $（$ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $）——第 $ i $ 个查询中的索引。
**输出格式**
输出 $ Q+1 $ 行。第一行包含一个整数，表示数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。对于每个 $ 1 \leq i \leq Q $，第 $ i+1 $ 行包含一个整数，表示 $ A_{P_i} $ 的值。
**输入输出样例**
**输入样例 #1**
```
6 3
1
4
5
```
**输出样例 #1**
```
17
1
3
4
```
**输入样例 #2**
```
1 0
```
**输出样例 #2**
```
1
```
**说明**
在第一个例子中，获得的数组 $ A $ 为 $ [1, 2, 3, 3, 4, 4] $。通过以下操作，我们可以看到数组是可排序的：
- 选择索引 $ 5 $，则 $ A = [1, 2, 3, 3, 6, 4] $。
- 选择索引 $ 6 $，则 $ A = [1, 2, 3, 3, 6, 6] $。
- 选择索引 $ 4 $，则 $ A = [1, 2, 3, 4, 6, 6] $。
- 选择索引 $ 6 $，则 $ A = [1, 2, 3, 4, 6, 8] $。**题意翻译** 给定一个数组 $ A $，可以通过以下操作使其变得单调递增：选择一个位置，将其值减去 $ 2^c $（其中 $ c $ 是之前在该位置上执行的操作次数），然后将结果乘以 2。若能通过一系列操作使得数组 $ A $ 单调递增，则称其为好的数组。现在需要构造一个长度为 $ n $ 的好的数组，使得数组元素之和 $ \sum A_i $ 最小，在此基础上使其字典序最小。输出 $ \sum A_i $，并根据 $ q $ 次询问输出对应位置的值，保证询问的位置是升序给出的。 其中 $ n \le 10^9 $，$ q \le \min(n, 10^5) $。 **题目描述** Pak Chanek有一个由 $ N $ 个正整数组成的数组 $ A $。Pak Chanek将对数组进行一系列操作，每次操作如下： 1. 选择一个索引 $ p $（$ 1 \leq p \leq N $）。 2. 设 $ c $ 为在此操作之前在索引 $ p $ 上执行的操作次数。 3. 将 $ A_p $ 的值减去 $ 2^c $。 4. 将 $ A_p $ 的值乘以 2。 每次操作后，数组 $ A $ 的所有元素都必须是正整数。 若Pak Chanek可以通过零次或多次操作使得 $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $，则称数组 $ A $ 是可排序的。 Pak Chanek必须找到一个可排序的数组 $ A $，其长度为 $ N $，使得 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ 的值最小。如果有多个这样的数组，Pak Chanek必须选择其中字典序最小的数组。 Pak Chanek必须解决以下问题： - 输出数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。 - 对于每个查询，输出对应位置 $ P_i $ 上的值 $ A_{P_i} $。 注意：若存在一个索引 $ i $，使得 $ B_i < C_i $ 且对于所有 $ j < i $ 都有 $ B_j = C_j $，则称大小为 $ N $ 的数组 $ B $ 在字典序上小于大小为 $ N $ 的数组 $ C $。 **输入输出格式** **输入格式** 第一行包含两个整数 $ N $ 和 $ Q $（$ 1 \leq N \leq 10^9 $，$ 0 \leq Q \leq \min(N, 10^5) $）——数组 $ A $ 的必要长度和查询的数量。 接下来的 $ Q $ 行中，第 $ i $ 行包含一个整数 $ P_i $（$ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $）——第 $ i $ 个查询中的索引。 **输出格式** 输出 $ Q+1 $ 行。第一行包含一个整数，表示数组 $ A $ 的元素和 $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $。对于每个 $ 1 \leq i \leq Q $，第 $ i+1 $ 行包含一个整数，表示 $ A_{P_i} $ 的值。 **输入输出样例** **输入样例 #1** ``` 6 3 1 4 5 ``` **输出样例 #1** ``` 17 1 3 4 ``` **输入样例 #2** ``` 1 0 ``` **输出样例 #2** ``` 1 ``` **说明** 在第一个例子中，获得的数组 $ A $ 为 $ [1, 2, 3, 3, 4, 4] $。通过以下操作，我们可以看到数组是可排序的： - 选择索引 $ 5 $，则 $ A = [1, 2, 3, 3, 6, 4] $。 - 选择索引 $ 6 $，则 $ A = [1, 2, 3, 3, 6, 6] $。 - 选择索引 $ 4 $，则 $ A = [1, 2, 3, 4, 6, 6] $。 - 选择索引 $ 6 $，则 $ A = [1, 2, 3, 4, 6, 8] $。