Reverse and Swap (Codeforces 1401F)
Tags: Others, bitmasks

You are given an array $$$a$$$ of length $$$2^n$$$. You should process $$$q$$$ queries on it. Each query has one of the following $$$4$$$ types:   $$$Replace(x, k)$$$ — change $$$a_x$$$ to $$$k$$$;  $$$Reverse(k)$$$ — reverse each subarray $$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);  $$$Swap(k)$$$ — swap subarrays $$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$$ and $$$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);  $$$Sum(l, r)$$$ — print the sum of the elements of subarray $$$[l, r]$$$. Write a program that can quickly process given queries.

Input: The first line contains two integers $$$n$$$, $$$q$$$ ($$$0 \le n \le 18$$$; $$$1 \le q \le 10^5$$$) — the length of array $$$a$$$ and the number of queries.The second line contains $$$2^n$$$ integers $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 10^9$$$).Next $$$q$$$ lines contains queries — one per line. Each query has one of $$$4$$$ types:   "$$$1$$$ $$$x$$$ $$$k$$$" ($$$1 \le x \le 2^n$$$; $$$0 \le k \le 10^9$$$) — $$$Replace(x, k)$$$;  "$$$2$$$ $$$k$$$" ($$$0 \le k \le n$$$) — $$$Reverse(k)$$$;  "$$$3$$$ $$$k$$$" ($$$0 \le k < n$$$) — $$$Swap(k)$$$;  "$$$4$$$ $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le 2^n$$$) — $$$Sum(l, r)$$$. It is guaranteed that there is at least one $$$Sum$$$ query.

Output: Print the answer for each $$$Sum$$$ query.

Note: In the first sample, initially, the array $$$a$$$ is equal to $$$\{7,4,9,9\}$$$.After processing the first query. the array $$$a$$$ becomes $$$\{7,8,9,9\}$$$.After processing the second query, the array $$$a_i$$$ becomes $$$\{9,9,7,8\}$$$Therefore, the answer to the third query is $$$9+7+8=24$$$.In the second sample, initially, the array $$$a$$$ is equal to $$$\{7,0,8,8,7,1,5,2\}$$$. What happens next is:   $$$Sum(3, 7)$$$ $$$\to$$$ $$$8 + 8 + 7 + 1 + 5 = 29$$$;  $$$Reverse(1)$$$ $$$\to$$$ $$$\{0,7,8,8,1,7,2,5\}$$$;  $$$Swap(2)$$$ $$$\to$$$ $$$\{1,7,2,5,0,7,8,8\}$$$;  $$$Sum(1, 6)$$$ $$$\to$$$ $$$1 + 7 + 2 + 5 + 0 + 7 = 22$$$;  $$$Reverse(3)$$$ $$$\to$$$ $$$\{8,8,7,0,5,2,7,1\}$$$;  $$$Replace(5, 16)$$$ $$$\to$$$ $$$\{8,8,7,0,16,2,7,1\}$$$;  $$$Sum(8, 8)$$$ $$$\to$$$ $$$1$$$;  $$$Swap(0)$$$ $$$\to$$$ $$$\{8,8,0,7,2,16,1,7\}$$$. 

Sample Inputs:
2 3
7 4 9 9
1 2 8
3 1
4 2 4

3 8
7 0 8 8 7 1 5 2
4 3 7
2 1
3 2
4 1 6
2 3
1 5 16
4 8 8
3 0

Sample Outputs:
24

29
22
1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def update(i, x):
    i += l1
    tree[i] = x
    i >>= 1
    while i:
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i >>= 1
    return
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
pow2 = [1]
for _ in range(n):
    pow2.append(2 * pow2[-1])
sp = list(pow2)
for i in range(1, n + 1):
    sp[i] += sp[i - 1]
l1 = pow2[n]
l2 = 2 * l1
tree = [0] * l2
for i in range(pow2[n]):
    tree[i + l1] = a[i]
for i in range(l1 - 1, 0, -1):
    tree[i] = tree[2 * i] + tree[2 * i + 1]
z = 0
ans = []
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        (x, k) = (t[1] - 1 ^ z, t[2])
        update(x, k)
        a[x] = k
    elif t[0] == 2:
        k = t[1]
        if k:
            z ^= sp[k - 1]
    elif t[0] == 3:
        k = t[1]
        z ^= pow2[k]
    else:
        (l, r) = (t[1] - 1, t[2])
        ans0 = 0
        (u, x) = (sp[-1], l1)
        for i in range(n + 1):
            if l & pow2[i] and l + pow2[i] <= r:
                ans0 += tree[x ^ (l ^ u & z) >> i]
                l += pow2[i]
            if r & pow2[i] and l <= r - pow2[i]:
                r -= pow2[i]
                ans0 += tree[x ^ (r ^ u & z) >> i]
            u ^= pow2[i]
            x >>= 1
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
QueryList = [0] * n
SegmentTree = []
a = list(map(int, input().split()))
for i in range(n + 1):
    SegmentTree.append([0] * (1 << n - i))
for i in range(1 << n):
    for j in range(n + 1):
        SegmentTree[j][i >> j] += a[i]

def FindSum(m):
    summ = 0
    for i in range(n + 1):
        if m & 1 << i:
            m -= 1 << i
            mCpy = m
            for j in range(i, n):
                if QueryList[j]:
                    mCpy ^= (1 << j + 1) - (1 << i)
            summ += SegmentTree[i][mCpy >> i]
    return summ
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        loc = t[1] - 1
        for i in range(n):
            if QueryList[i]:
                loc ^= (1 << i + 1) - 1
        increment = t[2] - SegmentTree[0][loc]
        for j in range(n + 1):
            SegmentTree[j][loc >> j] += increment
    if t[0] == 2:
        if t[1] == 0:
            continue
        QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
    if t[0] == 3:
        QueryList[t[1]] = 1 - QueryList[t[1]]
        if t[1] == 0:
            continue
        QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
    if t[0] == 4:
        print(FindSum(t[2]) - FindSum(t[1] - 1))

Solution (Python):
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
QueryList = [0] * n
SegmentTree = []
a = list(map(int, input().split()))
for i in range(n + 1):
    SegmentTree.append([0] * (1 << n - i))
for i in range(1 << n):
    for j in range(n + 1):
        SegmentTree[j][i >> j] += a[i]

def FindSum(m):
    summ = 0
    for i in range(n + 1):
        if m & 1 << i:
            m -= 1 << i
            mCpy = m
            for j in range(i, n):
                if QueryList[j]:
                    mCpy ^= (1 << j + 1) - (1 << i)
            summ += SegmentTree[i][mCpy >> i]
    return summ
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        loc = t[1] - 1
        for i in range(n):
            if QueryList[i]:
                loc ^= (1 << i + 1) - 1
        increment = t[2] - SegmentTree[0][loc]
        for j in range(n + 1):
            SegmentTree[j][loc >> j] += increment
    if t[0] == 2:
        if t[1] == 0:
            continue
        QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
    if t[0] == 3:
        QueryList[t[1]] = 1 - QueryList[t[1]]
        if t[1] == 0:
            continue
        QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
    if t[0] == 4:
        print(FindSum(t[2]) - FindSum(t[1] - 1))