codeforces#P1716E. Swap and Maximum Block
Swap and Maximum Block
Description
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.
Input
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.
Output
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.
Samples
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
18
8
13
Note
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]$.