首页 > 试题广场 >

或和异或

[编程题]或和异或

热度指数：82 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

首先给出一个长度为2ⁿ的序列 $A=\left\{ a_1, a_2, ..., a_{2^n-1}, a_{2^n} \right\}$ ，我们定义一个值v，这个值是由如下计算方法得到的，首先将A序列的第2*i-1位和第2*i位(i=1,2,..,2^n-1)进行OR操作得到新数列A'，然后再对A'序列操作，将A' 序列的第2*i位和第2*i-1位(i=1,2,...,2^n-2)进行XOR操作得到A''，对A''按照第一次操作方式进行OR操作，因为序列长度为2ⁿ,所以显然进行n次操作之后就只剩下一个数字了此时这个数字就是v。

例如A={1，2，3，4}，第一次操作之后为{1|2=3，3|4=7}，第二次操作后，{3^7=4},所以v=4。

但是显然事情并没有那么简单，给出A序列后，还有m个操作，每个操作表示为“a b”，表示将A[a]改为b，之后再对A序列求v值。

输入描述:

输入第一行包含两个正整数n，m，分别表示A序列的长度为2^n,操作数量为m。（1<=n<=17,1<=m<=10^5）
输入第二行包含n个正整数，中间用空格隔开，表示A序列。（0<=ai<=2^30）
接下来有m行，每行包含两个正整数a，b，表示一次操作，即把A[a]变成b。(1<=a<=2^n, 0<=b<=2^30)