AT_abc185_f [ABC185F] Range Xor Query

题目描述

有一个长度为 $N$ 的整数序列 $A$。
你需要对该序列处理 $Q$ 个查询。对于第 $i$ 个查询，给定 $T_i,\ X_i,\ Y_i$，请按如下方式进行操作：

• 当 $T_i = 1$ 时
  用 $A_{X_i} \oplus Y_i$ 替换 $A_{X_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$ 的按位异或。
按位异或的定义如下：对于整数 $A, B$，它们的按位异或 $A \oplus B$，在二进制表示下，对于每一位 $2^k$（$k \geq 0$），如果 $A$ 和 $B$ 的该位中只有一个是 $1$，则结果的该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$
$A_1\ \ A_2\ \ A_3\ \ \dots\ \ A_N$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$T_3$ $X_3$ $Y_3$
$\vdots$
$T_Q$ $X_Q$ $Y_Q$

输出格式

对于每个 $T_i = 2$ 的查询，按顺序每行输出一个答案。

输入输出样例 #1

输入 #1

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

输出 #1

0
1
2

输入输出样例 #2

输入 #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

输出 #2

1
0
5
3
0

说明/提示

数据范围

• $1 \leq N \leq 300000$
• $1 \leq Q \leq 300000$
• $0 \leq A_i < 2^{30}$
• $T_i$ 取 $1$ 或 $2$
• 若 $T_i = 1$，则 $1 \leq X_i \leq N$ 且 $0 \leq Y_i < 2^{30}$
• 若 $T_i = 2$，则 $1 \leq X_i \leq Y_i \leq N$
• 所有输入均为整数

样例解释 1

第 $1$ 个查询输出 $1 \oplus 2 \oplus 3 = 0$。
第 $2$ 个查询输出 $2 \oplus 3 = 1$。
第 $3$ 个查询将 $A_2$ 替换为 $2 \oplus 3 = 1$。
第 $4$ 个查询输出 $1 \oplus 3 = 2$。

由 ChatGPT 4.1 翻译