https://codeforces.com/problemset/problem/339/D
题意：2^n个数组成的数组，m次单点修改带查询。数组计算规则是相邻两数先做或运算得到新数组，新数组相邻两数再做异或运算，... ，最后得到一个数即为查询结果。
看到单点修改首先想到线段树或树状数组，再观察到2^n形式正好是一颗满节点的线段树，运算选择取决于线段树层数，叶子节点上一层或运算，再上一层异或，...，询问结果实际是问根节点的值
因此在单点修改的线段树模板上只需要根据层数切换update的方式即可
import sys
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
st = {}
x = n
res = 0
while x >= 0:
st[int(pow(2, x))] = (res ^ 1)
x -= 1
res ^= 1
def check(num):
x = 0
while x <= n:
i = int(pow(2, x))
j = int(pow(2, x + 1))
if i <= num < j:
return st[i]
x += 1
class sengment_tree:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums
self.tree = [0] * 4 * self.n
def update(self, root):
if check(root) == 1:
self.tree[root] = self.tree[root * 2] ^ self.tree[root * 2 + 1]
else:
self.tree[root] = self.tree[root * 2] | self.tree[root * 2 + 1]
def build(self, left, right, root):
if left == right:
self.tree[root] = self.nums[left - 1]
return
mid = (left + right) // 2
self.build(left, mid, root * 2)
self.build(mid + 1, right, root * 2 + 1)
self.update(root)
def change(self, pos, v, left, right, root):
if left == right:
self.tree[root] = v
return
mid = (left + right) // 2
if pos <= mid:
self.change(pos, v, left, mid, root * 2)
if pos >= mid + 1:
self.change(pos, v, mid + 1, right, root * 2 + 1)
self.update(root)
def query(self, A, B, left, right, root):
if A <= left <= right <= B:
return self.tree[root]
mid = (left + right) // 2
res = 0
if A <= mid:
if check(root):
res ^= self.query(A, B, left, mid, root * 2)
else:
res |= self.query(A, B, left, mid, root * 2)
if B >= mid + 1:
if check(root):
res ^= self.query(A, B, mid + 1, right, root * 2 + 1)
else:
res |= self.query(A, B, mid + 1, right, root * 2 + 1)
return res
tree = sengment_tree(a)
tree.build(1, int(pow(2, n)), 1)
for _ in range(m):
p, b = map(int, sys.stdin.readline().split())
tree.change(p, b, 1,int(pow(2, n)), 1)
res = tree.query(1, int(pow(2, n)), 1, int(pow(2, n)), 1)
print(res)