CF339D Xenia and Bit Operations

初学程序员 Xenia 有一个序列 $a$，包含 $2^{n}$ 个非负整数：$a_1, a_2, \ldots, a_{2^n}$。Xenia 正在学习位运算。为了更好地理解位运算，她决定计算该序列的一个值 $v$。 具体来说，计算值 $v$ 需要进行若干次迭代。第一次迭代，Xenia 记录一个新序列：$a_1 \,\text{or}\, a_2,\, a_3 \,\text{or}\, a_4,\, \ldots,\, a_{2^n-1} \,\text{or}\, a_{2^n}$，新序列共 $2^{n-1}$ 个元素。也就是说，她写下了原序列每一对相邻元素按位或（OR）的结果。第二次迭代，她对第一次迭代得到的新序列的相邻元素分别进行按位异或（XOR）操作。第三次迭代，Xenia 又对新序列的相邻元素进行按位或操作。如此交替进行，每次交替“按位或”和“按位异或”，直到剩下的序列只含有一个元素，该元素即为 $v$。 举个例子，假设序列 $a=(1,2,3,4)$。则所有变换过程为：$(1,2,3,4) \rightarrow (1\,\text{or}\,2=3,\,3\,\text{or}\,4=7) \rightarrow (3\,\text{xor}\,7=4)$。最终结果为 $v=4$。 给定 Xenia 的初始序列。为了增加难度，你还将得到 $m$ 个额外的操作。每次操作给定一对整数 $p, b$，表示执行赋值 $a_p = b$。每次操作后，你需要输出当前序列 $a$ 计算得到的新值 $v$。

第一行包含两个整数 $n$ 和 $m$，$1 \leq n \leq 17,\, 1 \leq m \leq 10^5$。第二行包含 $2^{n}$ 个整数 $a_1, a_2, \ldots, a_{2^n}$，$0 \leq a_i < 2^{30}$。接下来 $m$ 行，每行包含一个操作，第 $i$ 行给出两个整数 $p_i, b_i$，$1 \leq p_i \leq 2^n,\, 0 \leq b_i < 2^{30}$。

输出 $m$ 行，每行一个整数，第 $i$ 行表示执行第 $i$ 次操作后，序列 $a$ 当前对应的值 $v$。

更多有关位运算的信息，可以参考此链接：http://en.wikipedia.org/wiki/Bitwise\_operation。 由 ChatGPT 5 翻译