Swap and Maximum Block (Codeforces 1716E)
Tags: DP, divide and conquer

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: 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.

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

Sample Inputs:
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1

Sample Outputs:
18
8
13

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(float, input().split()))
(dp0, dps0) = (list(a), list(a))
(dpl0, dpr0) = (list(a), list(a))
pow2 = [1]
for _ in range(n):
    pow2.append(2 * pow2[-1])
m = pow2[n]
for _ in range(n):
    (dp, dps) = ([0] * m, [0] * m)
    (dpl, dpr) = ([0] * m, [0] * m)
    for i in range(m // 2):
        (j, k) = (2 * i, 2 * i + 1)
        dp[i] = max(dp0[j], dp0[k], dpr0[j] + dpl0[k])
        dps[i] = dps0[j] + dps0[k]
        dpl[i] = max(dpl0[j], dps0[j] + dpl0[k])
        dpr[i] = max(dpr0[k], dps0[k] + dpr0[j])
    for i in range(m // 2, m):
        (j, k) = (2 * i + 1 - m, 2 * i - m)
        dp[i] = max(dp0[j], dp0[k], dpr0[j] + dpl0[k])
        dps[i] = dps0[j] + dps0[k]
        dpl[i] = max(dpl0[j], dps0[j] + dpl0[k])
        dpr[i] = max(dpr0[k], dps0[k] + dpr0[j])
    (dp0, dps0) = (dp, dps)
    (dpl0, dpr0) = (dpl, dpr)
dp = [max(int(i), 0) for i in dp]
q = int(input())
ans = []
x = 0
for _ in range(q):
    k = int(input())
    x ^= pow2[k]
    ans0 = dp[x]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
n = int(input())
m = 1 << n
a = list(map(int, input().split()))
(SUM, pref, suff, ans) = ([0] * m, [0] * m, [0] * m, [0] * m)
for i in range(m):
    SUM[i] = a[i]
    pref[i] = max(0, a[i])
    suff[i] = max(0, a[i])
    suff[i] = max(0, a[i])
for i in range(n):
    (nSUM, npref, nsuff, nans) = ([0] * m, [0] * m, [0] * m, [0] * m)
    for j in range(m):
        L = j
        R = j ^ 1 << i
        nSUM[j] = SUM[L] + SUM[R]
        npref[j] = max(pref[L], SUM[L] + pref[R])
        nsuff[j] = max(suff[R], suff[L] + SUM[R])
        nans[j] = max(ans[L], ans[R], pref[R] + suff[L])
    (SUM, pref, suff, ans) = (nSUM, npref, nsuff, nans)
XOR = 0
q = int(input())
for _ in range(q):
    k = int(input())
    XOR ^= 1 << k
    print(ans[XOR])

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
(dp0, dps0) = (list(a), list(a))
(dpl0, dpr0) = (list(a), list(a))
pow2 = [1]
for _ in range(n):
    pow2.append(2 * pow2[-1])
m = pow2[n]
for _ in range(n):
    (dp, dps) = ([0] * m, [0] * m)
    (dpl, dpr) = ([0] * m, [0] * m)
    for i in range(m // 2):
        (j, k) = (2 * i, 2 * i + 1)
        dp[i] = max(dp0[j], dp0[k], dpr0[j] + dpl0[k])
        dps[i] = dps0[j] + dps0[k]
        dpl[i] = max(dpl0[j], dps0[j] + dpl0[k])
        dpr[i] = max(dpr0[k], dps0[k] + dpr0[j])
    for i in range(m // 2, m):
        (j, k) = (2 * i + 1 - m, 2 * i - m)
        dp[i] = max(dp0[j], dp0[k], dpr0[j] + dpl0[k])
        dps[i] = dps0[j] + dps0[k]
        dpl[i] = max(dpl0[j], dps0[j] + dpl0[k])
        dpr[i] = max(dpr0[k], dps0[k] + dpr0[j])
    (dp0, dps0) = (dp, dps)
    (dpl0, dpr0) = (dpl, dpr)
dp = [max(i, 0) for i in dp]
q = int(input())
ans = []
x = 0
for _ in range(q):
    k = int(input())
    x ^= pow2[k]
    ans0 = dp[x]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))