AT_abc185_f [ABC185F] Range Xor Query
题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an,你需要依次处理 q 个查询。第 i 个查询给定 ti,xi,yi,按如下规则执行:
∙若 ti=1,将 axi 替换为 axixoryi;
∙若 ti=2,输出 $a_{x_i} \operatorname{xor} a_{x_i + 1} \operatorname{xor} \dots \operatorname{xor} a_{y_i}$ 的值。
其中 xor 表示按位异或运算。对于整数 u,v,它们的按位异或 uxorv 在二进制表示下满足:对于每一位 2k(k≧0),若 u 和 v 在该位中恰好有一个为 1,则结果的该位为 1;否则结果的该位为 0。
例如,3xor5=6,因为二进制下 011xor101=110。
输入格式
第一行输入两个整数 n,q(1≦n,q≦3×105) 分别代表序列长度和查询数量。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i < 2^{30}\right)$ 代表序列的初始值。
此后 q 行,第 i 行输入三个整数 $t_i, x_i, y_i \left(t_i \in \{1, 2\};\ 1 \leqq x_i \leqq n\right)$ 代表第 i 个查询,其中 yi 的含义与范围取决于 ti:
∙若 ti=1,则 0≦yi<230,本次查询将 axi 替换为 axixoryi;
∙若 ti=2,则 xi≦yi≦n,本次查询询问区间 [xi,yi] 内所有元素的异或和。
输出格式
对于每个 ti=2 的查询,按查询顺序新起一行输出一个整数,代表该次询问得到的异或和。
测试样例
3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3
0
1
2
样例 1 解释
序列的初始值为 {1,2,3}。
∙第 1 个查询:1xor2xor3=0;
∙第 2 个查询:2xor3=1;
∙第 3 个查询:将 a2 替换为 2xor3=1,此时序列变为 {1,1,3};
∙第 4 个查询:1xor3=2。
因此依次输出 0,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