← 返回题目列表

Codeforces · 1725/D

D. 推导可排序性

中文机器翻译题面 查看原题

假设 Pak Chanek 有一个由 $$$N$$$ 正整数组成的数组 $$$A$$$。 Pak Chanek 将进行多项手术。在每次行动中,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 必须找到一个可排序且长度为 $$$N$$$ 的数组 $$$A$$$,使得 $$$A_1 + A_2 + A_3 + A_4 + \ldots + A_N$$$ 是可能的最小值。如果存在不止一种可能性,Pak Chanek 必须选择其中字典顺序最小的数组。

Pak Chanek 必须解决以下问题:

- Pak Chanek 必须打印该数组的 $$$A_1 + A_2 + A_3 + A_4 + \ldots + A_N$$$ 的值。
- 将给出 $$$Q$$$ 问题。对于第 $$$i$$$ 问题,给出一个整数 $$$P_i$$$。 Pak Chanek 必须打印 $$$A_{P_i}$$$ 的值。

帮助 Pak Chanek 解决问题。

注意:当且仅当存在索引 $$$i$$$ 使得 $$$B_i < C_i$$$ 且对于每个 $$$j < i$$$,$$$B_j = C_j$$$。

输入

第一行包含两个整数 $$$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$$$ 行。 $$$1$$$-st 行包含一个表示 $$$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]$$$。