Range Xor Query

题目描述

我们有一个长度为 $N$ 的整数序列 $A$.
你将对该序列处理 $Q$ 个查询。在第 $i$ 个查询中，给定数值 $T_i$、$X_i$ 和 $Y_i$，执行以下操作：

如果 $T_i = 1$，将 $A_{X_i}$ 替换为 $A_{X_i} \oplus Y_i$。 如果 $T_i = 2$，输出 $A_{X_i} \oplus A_{X_i + 1} \oplus A_{X_i + 2} \oplus \dots \oplus A_{Y_i}$。

这里，$a \oplus b$ 表示 $a$ 和 $b$ 的按位异或。

输入格式

Input is given from Standard Input in the following format: $N$ $Q$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ $T_1$ $X_1$ $Y_1$ $T_2$ $X_2$ $Y_2$ $T_3$ $X_3$ $Y_3$ $\hspace{22pt} \vdots$ $T_Q$ $X_Q$ $Y_Q$

输出格式

对于每个按接收顺序出现且满足 $T_i = 2$ 的查询，在单独的一行中输出对应的结果。

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

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

提示

$1 \le N \le 300000$ $1 \le Q \le 300000$ $0 \le A_i \lt 2^{30}$ $T_i$ is $1$ or $2$. If $T_i = 1$, then $1 \le X_i \le N$ and $0 \le Y_i \lt 2^{30}$. If $T_i = 2$, then $1 \le X_i \le Y_i \le N$. All values in input are integers.在第一个查询中，我们输出 $1 \oplus 2 \oplus 3 = 0$.
在第二个查询中，我们输出 $2 \oplus 3 = 1$.
在第三个查询中，我们将 $A_2$ 替换为 $2 \oplus 3 = 1$.
在第四个查询中，我们输出 $1 \oplus 3 = 2$.

标签: AtCoder|abc185F

来源

AtCoder|abc185F