CF1725D Deducing Sortability

假设 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 需要解决以下问题： - 输出该数组的 $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$ 的值。 - 给定 $Q$ 个问题，对于第 $i$ 个问题，给定一个整数 $P_i$，Pak Chanek 需要输出 $A_{P_i}$ 的值。 请帮助 Pak Chanek 解决这个问题。 注意：如果存在两个大小为 $N$ 的数组 $B$ 和 $C$，若存在某个下标 $i$ 使得 $B_i < C_i$，且对于所有 $j < i$，都有 $B_j = C_j$，则称 $B$ 的字典序小于 $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_1 + A_2 + A_3 + A_4 + \ldots + A_N$ 的值。对于每个 $1 \leq i \leq Q$，第 $(i+1)$ 行输出 $A_{P_i}$ 的值。

在第一个样例中，得到的数组 $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]$。 由 ChatGPT 4.1 翻译