#ABC185F. 区间异或询问

区间异或询问

AT_abc185_f [ABC185F] Range Xor Query

题目描述

\hspace{15pt}给定一个长度为 nn 的整数序列 a1,a2,…,ana_1, a_2, \dots, a_n,你需要依次处理 qq 个查询。第 ii 个查询给定 ti,xi,yit_i, x_i, y_i,按如下规则执行:

∙ \hspace{23pt}\bullet\,若 ti=1t_i = 1,将 axia_{x_i} 替换为 axixor⁡yia_{x_i} \operatorname{xor} y_i;

∙ \hspace{23pt}\bullet\,若 ti=2t_i = 2,输出 $a_{x_i} \operatorname{xor} a_{x_i + 1} \operatorname{xor} \dots \operatorname{xor} a_{y_i}$ 的值。

\hspace{15pt}其中 xor⁡\operatorname{xor} 表示按位异或运算。对于整数 u,vu, v,它们的按位异或 uxor⁡vu \operatorname{xor} v 在二进制表示下满足:对于每一位 2k(k≧0)2^k \left(k \geqq 0\right),若 uu 和 vv 在该位中恰好有一个为 11,则结果的该位为 11;否则结果的该位为 00。

\hspace{15pt}例如,3xor⁡5=63 \operatorname{xor} 5 = 6,因为二进制下 011xor⁡101=110011 \operatorname{xor} 101 = 110。

输入格式

\hspace{15pt}第一行输入两个整数 n,q(1≦n,q≦3×105)n, q \left(1 \leqq n, q \leqq 3 \times 10^5\right) 分别代表序列长度和查询数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i < 2^{30}\right)$ 代表序列的初始值。

\hspace{15pt}此后 qq 行,第 ii 行输入三个整数 $t_i, x_i, y_i \left(t_i \in \{1, 2\};\ 1 \leqq x_i \leqq n\right)$ 代表第 ii 个查询,其中 yiy_i 的含义与范围取决于 tit_i:

∙ \hspace{23pt}\bullet\,若 ti=1t_i = 1,则 0≦yi<2300 \leqq y_i < 2^{30},本次查询将 axia_{x_i} 替换为 axixor⁡yia_{x_i} \operatorname{xor} y_i;

∙ \hspace{23pt}\bullet\,若 ti=2t_i = 2,则 xi≦yi≦nx_i \leqq y_i \leqq n,本次查询询问区间 [xi,yi]\left[x_i, y_i\right] 内所有元素的异或和。

输出格式

\hspace{15pt}对于每个 ti=2t_i = 2 的查询,按查询顺序新起一行输出一个整数,代表该次询问得到的异或和。

测试样例

3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3
0
1
2

样例 1 解释

\hspace{15pt}序列的初始值为 {1,2,3}\{1, 2, 3\}。

∙ \hspace{23pt}\bullet\,第 11 个查询:1xor⁡2xor⁡3=01 \operatorname{xor} 2 \operatorname{xor} 3 = 0;

∙ \hspace{23pt}\bullet\,第 22 个查询:2xor⁡3=12 \operatorname{xor} 3 = 1;

∙ \hspace{23pt}\bullet\,第 33 个查询:将 a2a_2 替换为 2xor⁡3=12 \operatorname{xor} 3 = 1,此时序列变为 {1,1,3}\{1, 1, 3\};

∙ \hspace{23pt}\bullet\,第 44 个查询:1xor⁡3=21 \operatorname{xor} 3 = 2。

\hspace{15pt}因此依次输出 0,1,20, 1, 2。

10 10
0 5 3 4 7 0 0 0 1 0
1 10 7
2 8 9
2 3 6
2 1 6
2 1 10
1 9 4
1 6 1
1 6 3
1 1 7
2 3 5
1
0
5
3
0