/ CWOI / 题库 /

2017.07.18 P2 位运算

2017.07.18 P2 位运算

题目描述

xenia 是一名初级程序员,他有一个由 \(2^n\) 个非负整数的序列 a:\(a_1\), \(a_2\),…, \(a_{2^n}\)。xenia 目前正在研究位运算,为了更好的了解它们的工作,xenia 打算去计算某些值 v。他需要多次运算才能得到 v 值。
例如序列 a = {1, 2, 3, 4}:
第一步:将相邻元素进行 OR 运算,(1 or 2 = 3, 3 or 4 = 7);
第二步:将相邻元素进行 XOR 运算,(3 xor 7 = 4);
第三步:重复 2, 3 步,直到得到 v。
简单来说就是 OR, XOR 这两种运算符的交替运算,然后输出最终的数值。
再给出 m 个更新,每次更新一对整数 p, b,将 p 位置的值改为 b。对于每次更新,输出整个序列的 v 值。

输入格式

第一行两个整数 n, m;
第二行 \(2^n\) 个整数 \(a_1\), \(a_2\), …, \(a_{2^n}\);
接下来 m 个更新 \(p_i\), \(b_i\)。

输出格式

对于每个更新,输出整个序列的 v 值。

样例1

输入

2 4
1 6 3 5
1 4
3 4
1 2
1 2

输出

1
3
3
3

数据范围

对于 30%的数据,1 \(\leq\) n \(\leq\) 5, 1 \(\leq\) m \(\leq\) 20,0 \(\leq\) ai < 50,1 \(\leq\) \(p_i\) \(\leq\) \(2^n\), 0 \(\leq\) \(b_i\) < 50;
对于 100%的数据,1 \(\leq\) n \(\leq\) 17, 1 \(\leq\) m \(\leq\) \(10^5\),0 \(\leq\) \(a_i\) < 230,1 \(\leq\) \(p_i\) \(\leq\) \(2^n\), 0 \(\leq\) \(b_i\) < \(2^{30}\)。

限制

1s, 256M

来源

Codeforces339D
CWOI新高二专题测试十五

信息

难度
2
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
10
已通过
8
通过率
80%
上传者