CF1716E Swap and Maximum Block

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.

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] $ .