CF1401F Reverse and Swap

给定一个长度为 $2^n$ 的数组 $a$，你需要对其进行 $q$ 次操作。每次操作有以下四种类型之一： 1. $Replace(x, k)$ —— 将 $a_x$ 修改为 $k$； 2. $Reverse(k)$ —— 对所有 $i$（$i \ge 1$），将子数组 $[(i-1) \cdot 2^k+1,\, i \cdot 2^k]$ 进行反转； 3. $Swap(k)$ —— 对所有 $i$（$i \ge 1$），交换子数组 $[(2i-2) \cdot 2^k+1,\, (2i-1) \cdot 2^k]$ 和 $[(2i-1) \cdot 2^k+1,\, 2i \cdot 2^k]$； 4. $Sum(l, r)$ —— 输出子数组 $[l, r]$ 的元素和。 请编写程序高效地处理所有操作。

第一行包含两个整数 $n$、$q$（$0 \le n \le 18$；$1 \le q \le 10^5$），分别表示数组 $a$ 的长度的对数和操作次数。 第二行包含 $2^n$ 个整数 $a_1, a_2, \ldots, a_{2^n}$（$0 \le a_i \le 10^9$）。 接下来的 $q$ 行，每行一个操作，格式如下： - “$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)$。 保证至少有一个 $Sum$ 操作。

对于每个 $Sum$ 操作，输出一行答案。

在第一个样例中，初始数组 $a$ 为 $\{7,4,9,9\}$。 处理第一个操作后，数组 $a$ 变为 $\{7,8,9,9\}$。 处理第二个操作后，数组 $a$ 变为 $\{9,9,7,8\}$。 因此，第三个操作的答案为 $9+7+8=24$。 在第二个样例中，初始数组 $a$ 为 $\{7,0,8,8,7,1,5,2\}$。之后的操作如下： 1. $Sum(3, 7)$ $\to$ $8 + 8 + 7 + 1 + 5 = 29$； 2. $Reverse(1)$ $\to$ $\{0,7,8,8,1,7,2,5\}$； 3. $Swap(2)$ $\to$ $\{1,7,2,5,0,7,8,8\}$； 4. $Sum(1, 6)$ $\to$ $1 + 7 + 2 + 5 + 0 + 7 = 22$； 5. $Reverse(3)$ $\to$ $\{8,8,7,0,5,2,7,1\}$； 6. $Replace(5, 16)$ $\to$ $\{8,8,7,0,16,2,7,1\}$； 7. $Sum(8, 8)$ $\to$ $1$； 8. $Swap(0)$ $\to$ $\{8,8,0,7,2,16,1,7\}$。 由 ChatGPT 4.1 翻译