CF1716E Swap and Maximum Block

给定一个长度为 $2^n$ 的数组。数组中的元素从 $1$ 到 $2^n$ 编号。 你需要对该数组处理 $q$ 次查询。在第 $i$ 次查询中，你会得到一个整数 $k$（$0 \le k \le n-1$）。处理该查询时，你需要执行以下操作： - 对于每个 $i \in [1, 2^n-2^k]$（按升序），执行如下操作：如果第 $i$ 个元素在本次查询中已经和其他元素交换过，则跳过；否则，将 $a_i$ 与 $a_{i+2^k}$ 交换； - 完成上述操作后，输出数组所有连续子段（包括空子段）中的最大和。 例如，若数组 $a$ 为 $[-3, 5, -3, 2, 8, -20, 6, -1]$，且 $k=1$，则本次查询的处理过程如下： - 第 $1$ 个元素尚未交换过，与第 $3$ 个元素交换； - 第 $2$ 个元素尚未交换过，与第 $4$ 个元素交换； - 第 $3$ 个元素已交换过，跳过； - 第 $4$ 个元素已交换过，跳过； - 第 $5$ 个元素尚未交换过，与第 $7$ 个元素交换； - 第 $6$ 个元素尚未交换过，与第 $8$ 个元素交换。 因此，数组变为 $[-3, 2, -3, 5, 6, -1, 8, -20]$。最大连续子段和为 $[5, 6, -1, 8]$，答案为 $18$。 注意，查询会实际改变数组，即每次查询后数组不会恢复到原始状态，下一次查询将在修改后的数组上进行。

第一行包含一个整数 $n$（$1 \le n \le 18$）。 第二行包含 $2^n$ 个整数 $a_1, a_2, \dots, a_{2^n}$（$-10^9 \le a_i \le 10^9$）。 第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。 接下来 $q$ 行，每行一个整数 $k$（$0 \le k \le n-1$），表示第 $i$ 次查询。

对于每次查询，输出一个整数，表示处理完该查询后数组所有连续子段（包括空子段）的最大和。

示例中的数组变化过程为：$[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]$。 由 ChatGPT 4.1 翻译