Swap and Maximum Block
Contest: Educational Codeforces Round 133 (Rated for Div. 2)
Difficulty rating: 2500
Tags: bitmasks, data structures, dfs and similar, divide and conquer, dp

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.

Input format:
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 format:
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example input:
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1

Example output:
18
8
13

Editorial:
Let's carefully analyze the operation denoted in the query. Since the length of the array is always divisible by $$$2^{k+1}$$$, every element will be swapped with some other element. The elements can be split into two groups — the ones whose positions increase by $$$2^k$$$, and the ones whose positions decrease by $$$2^k$$$.
Let's find some trait of the elements which will allow us to distinguish the elements of one group from the elements of the other group. The first $$$2^k$$$ elements will be shifted to the right, the next $$$2^k$$$ elements will be shifted to the left, the next $$$2^k$$$ elements will be shifted to the right, etc. If we look at the binary representations of integers $$$0, 1, \dots, n-1$$$, then we can see that the first $$$2^k$$$ elements have $$$0$$$ in the $$$k$$$-th bit, the next $$$2^k$$$ elements have $$$1$$$ in the $$$k$$$-th bit, the next $$$2^k$$$ elements have $$$0$$$ in the $$$k$$$-th bit, and so on. So, if we consider the positions of elements as $$$0$$$-indexed, then the operation can be described as follows: "Let the position of the element be $$$i$$$. If the $$$k$$$-th bit in $$$i$$$ is $$$0$$$, $$$i$$$ gets increased by $$$2^k$$$, otherwise $$$i$$$ gets decreased by $$$2^k$$$". What does it look like? Actually, it is just $$$i \oplus 2^k$$$ (where $$$\oplus$$$ denotes XOR).
So, each query can be represented as "swap $$$a_i$$$ with $$$a_{i \oplus x}$$$ for some integer $$$x$$$". The combination of two queries can also be represented with a single query; in fact, the state of the array can be denoted as the XOR of all $$$2^k$$$ from the previous queries.
Now, let's try to solve the following problem: for every $$$x \in [0, 2^n-1]$$$, calculate the maximum sum of subsegment if every element $$$a_i$$$ is swapped with $$$a_{i \oplus x}$$$. To solve this problem, we can use a segment tree.
First of all, we need to understand how to solve the problem of finding the maximum sum on subsegment using a segment tree. To do this, we should store the following four values in each vertex of the segment tree:
• $$$\mathit{sum}$$$ — the sum of elements on the segment denoted by the vertex;
• $$$\mathit{pref}$$$ — the maximum sum of elements on the prefix of the segment denoted by the vertex;
• $$$\mathit{suff}$$$ — the maximum sum of elements on the suffix of the segment denoted by the vertex;
• $$$\mathit{ans}$$$ — the answer on the segment.
If some vertex of the segment tree has two children, these values for it can be easily calculated using the values from the children. So, we can "glue" two segments represented by the vertices together, creating a new vertex representing the concatenation of these segments.
Okay, but how do we apply XOR to this? For every vertex of the segment tree, let's create several versions; the $$$x$$$-th version of the vertex $$$v$$$ represents the segment corresponding to this vertex if we apply swapping query with $$$x$$$ to it. For a vertex $$$v$$$ representing the segment of length $$$2^k$$$, we can use the following relation to get all its versions (here, we denote $$$t(v, x)$$$ as the $$$x$$$-th version of $$$v$$$, and $$$v_l$$$ and $$$v_r$$$ as the children of $$$v$$$):
• if $$$x \ge 2^{k-1}$$$, then $$$t(v, x) = \mathit{combine}(t(v_r, x-2^{k-1}), t(v_l, x-2^{k-1}))$$$;
• else $$$t(v, x) = \mathit{combine}(t(v_l, x), t(v_r, x))$$$;
The function $$$\mathit{combine}$$$ here denotes the "glueing together" of two vertices we described above.
Now let's try to analyze how many versions of each vertex we need. For the root, we will need all $$$2^n$$$ versions. For its children, we need only $$$2^{n-1}$$$ versions. For the children of the children of the root, we need only $$$2^{n-2}$$$ versions, and so on; so, overall, the total number of versions is only $$$O(n 2^n)$$$, and each version can be constructed in $$$O(1)$$$, so the solution works in $$$O(n 2^n)$$$.