309672: CF1716E. Swap and Maximum Block
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Swap and Maximum Block
题意翻译
你有一个长度是 $2^n$ 的序列 $a$ , 下标从 $1$ 到 $2^n$ . ( $n \le 18$ , $-10^9 \le a_i \le 10^9$ ) . 你需要对这个序列进行 $q$ ( $q \le 2 \times 10^5$ ) 次操作 , 每次操作你都会得到一个整数 $k$ ( $0 \le k \le n-1$ ) . 你需要进行如下操作 : - 对于 $\forall i \in [1,2^n-2^k]$ , 如果 $a_i$ 已经被交换过了 , 那么忽略它 ; 否则 , 将 $a_i$ 和 $a_{i+2^k}$ 进行交换 . - 在这之后 , 输出序列最大子段和 . 本题中 , 最大子段**可以一个数都不选** . 注意 , 每次操作之后不会撤销 .题目描述
You are given an array of length $ 2^n $ . The elements of the array are numbered from $ 1 $ to $ 2^n $ . You have to process $ q $ queries to this array. In the $ i $ -th query, you will be given an integer $ k $ ( $ 0 \le k \le n-1 $ ). To process the query, you should do the following: - for every $ i \in [1, 2^n-2^k] $ in ascending order, do the following: if the $ i $ -th element was already swapped with some other element during this query, skip it; otherwise, swap $ a_i $ and $ a_{i+2^k} $ ; - after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment). For example, if the array $ a $ is $ [-3, 5, -3, 2, 8, -20, 6, -1] $ , and $ k = 1 $ , the query is processed as follows: - the $ 1 $ -st element wasn't swapped yet, so we swap it with the $ 3 $ -rd element; - the $ 2 $ -nd element wasn't swapped yet, so we swap it with the $ 4 $ -th element; - the $ 3 $ -rd element was swapped already; - the $ 4 $ -th element was swapped already; - the $ 5 $ -th element wasn't swapped yet, so we swap it with the $ 7 $ -th element; - the $ 6 $ -th element wasn't swapped yet, so we swap it with the $ 8 $ -th element. So, the array becomes $ [-3, 2, -3, 5, 6, -1, 8, -20] $ . The subsegment with the maximum sum is $ [5, 6, -1, 8] $ , and the answer to the query is $ 18 $ . Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 1 \le n \le 18 $ ). The second line contains $ 2^n $ integers $ a_1, a_2, \dots, a_{2^n} $ ( $ -10^9 \le a_i \le 10^9 $ ). The third line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ). Then $ q $ lines follow, the $ i $ -th of them contains one integer $ k $ ( $ 0 \le k \le n-1 $ ) describing the $ i $ -th query.
输出格式
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.
输入输出样例
输入样例 #1
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1输出样例 #1
18
8
13说明
Transformation of the array in the example: $ [-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] $ .Input
题意翻译
你有一个长度是 $2^n$ 的序列 $a$ , 下标从 $1$ 到 $2^n$ . ( $n \le 18$ , $-10^9 \le a_i \le 10^9$ ) . 你需要对这个序列进行 $q$ ( $q \le 2 \times 10^5$ ) 次操作 , 每次操作你都会得到一个整数 $k$ ( $0 \le k \le n-1$ ) . 你需要进行如下操作 : - 对于 $\forall i \in [1,2^n-2^k]$ , 如果 $a_i$ 已经被交换过了 , 那么忽略它 ; 否则 , 将 $a_i$ 和 $a_{i+2^k}$ 进行交换 . - 在这之后 , 输出序列最大子段和 . 本题中 , 最大子段**可以一个数都不选** . 注意 , 每次操作之后不会撤销 .Output
**标题：交换与最大块**
**题意翻译：**
给定一个长度为 $2^n$ 的序列 $a$，下标从 1 到 $2^n$（$n \le 18$，$-10^9 \le a_i \le 10^9$）。
对这个序列进行 $q$（$q \le 2 \times 10^5$）次操作，每次操作都会得到一个整数 $k$（$0 \le k \le n-1$）。操作如下：
- 对于 $\forall i \in [1,2^n-2^k]$，如果 $a_i$ 已经被交换过，忽略它；否则，将 $a_i$ 和 $a_{i+2^k}$ 进行交换。
- 之后，输出序列最大子段和。注意，最大子段**可以一个数都不选**。
每次操作后不会撤销。
**题目描述：**
给定一个长度为 $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 \times 10^5$）。
接下来 $q$ 行，每行包含一个整数 $k$（$0 \le k \le n-1$），描述第 $i$ 个查询。
**输出格式：**
对于每个查询，输出一个整数，即处理查询后数组所有连续子段的最大和（包括空子段）。**标题：交换与最大块** **题意翻译：** 给定一个长度为 $2^n$ 的序列 $a$，下标从 1 到 $2^n$（$n \le 18$，$-10^9 \le a_i \le 10^9$）。 对这个序列进行 $q$（$q \le 2 \times 10^5$）次操作，每次操作都会得到一个整数 $k$（$0 \le k \le n-1$）。操作如下： - 对于 $\forall i \in [1,2^n-2^k]$，如果 $a_i$ 已经被交换过，忽略它；否则，将 $a_i$ 和 $a_{i+2^k}$ 进行交换。 - 之后，输出序列最大子段和。注意，最大子段**可以一个数都不选**。 每次操作后不会撤销。 **题目描述：** 给定一个长度为 $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 \times 10^5$）。 接下来 $q$ 行，每行包含一个整数 $k$（$0 \le k \le n-1$），描述第 $i$ 个查询。 **输出格式：** 对于每个查询，输出一个整数，即处理查询后数组所有连续子段的最大和（包括空子段）。
**题意翻译：**
给定一个长度为 $2^n$ 的序列 $a$，下标从 1 到 $2^n$（$n \le 18$，$-10^9 \le a_i \le 10^9$）。
对这个序列进行 $q$（$q \le 2 \times 10^5$）次操作，每次操作都会得到一个整数 $k$（$0 \le k \le n-1$）。操作如下：
- 对于 $\forall i \in [1,2^n-2^k]$，如果 $a_i$ 已经被交换过，忽略它；否则，将 $a_i$ 和 $a_{i+2^k}$ 进行交换。
- 之后，输出序列最大子段和。注意，最大子段**可以一个数都不选**。
每次操作后不会撤销。
**题目描述：**
给定一个长度为 $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 \times 10^5$）。
接下来 $q$ 行，每行包含一个整数 $k$（$0 \le k \le n-1$），描述第 $i$ 个查询。
**输出格式：**
对于每个查询，输出一个整数，即处理查询后数组所有连续子段的最大和（包括空子段）。**标题：交换与最大块** **题意翻译：** 给定一个长度为 $2^n$ 的序列 $a$，下标从 1 到 $2^n$（$n \le 18$，$-10^9 \le a_i \le 10^9$）。 对这个序列进行 $q$（$q \le 2 \times 10^5$）次操作，每次操作都会得到一个整数 $k$（$0 \le k \le n-1$）。操作如下： - 对于 $\forall i \in [1,2^n-2^k]$，如果 $a_i$ 已经被交换过，忽略它；否则，将 $a_i$ 和 $a_{i+2^k}$ 进行交换。 - 之后，输出序列最大子段和。注意，最大子段**可以一个数都不选**。 每次操作后不会撤销。 **题目描述：** 给定一个长度为 $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 \times 10^5$）。 接下来 $q$ 行，每行包含一个整数 $k$（$0 \le k \le n-1$），描述第 $i$ 个查询。 **输出格式：** 对于每个查询，输出一个整数，即处理查询后数组所有连续子段的最大和（包括空子段）。