A6905. 区间异或查询
编程题
普及/提高-
知识点
题目描述
有一个长度为 $N$ 的整数数组 $数组A$（下标从 $1$ 开始）。
你需要处理 $Q$ 次操作，每次操作是下面两种之一：
- $1\ x\ y$：把 $A[x]$ 更新成 $A[x]\oplus y$。
- $2\ l\ r$：输出 $A[l]\oplus A[l+1]\oplus \dots \oplus A[r]$。
其中 $\oplus$ 表示按位异或（bitwise XOR）。可以理解为：二进制每一位“相同为 $0$，不同为 $1$。
你需要处理 $Q$ 次操作，每次操作是下面两种之一：
- $1\ x\ y$：把 $A[x]$ 更新成 $A[x]\oplus y$。
- $2\ l\ r$：输出 $A[l]\oplus A[l+1]\oplus \dots \oplus A[r]$。
其中 $\oplus$ 表示按位异或（bitwise XOR）。可以理解为：二进制每一位“相同为 $0$，不同为 $1$。
输入格式
第一行输入 $N\ Q$。
第二行输入 $A_1\ A_2\ \dots\ A_N$。
接下来 $Q$ 行，每行一个查询：
- 如果 $T_i=1$：输入 $1\ X_i\ Y_i$
- 如果 $T_i=2$：输入 $2\ X_i\ Y_i$（表示 $l=X_i,\ r=Y_i$）
第二行输入 $A_1\ A_2\ \dots\ A_N$。
接下来 $Q$ 行，每行一个查询：
- 如果 $T_i=1$：输入 $1\ X_i\ Y_i$
- 如果 $T_i=2$：输入 $2\ X_i\ Y_i$（表示 $l=X_i,\ r=Y_i$）
输出格式
每当遇到 $T_i=2$ 的查询，输出一行答案。
输入输出样例
输入 #1
3 4 1 2 3 2 1 3 2 2 3 1 2 3 2 2 3
输出 #1
0 1 2
说明/提示
## 数据范围
- $1\le N\le 300000$
- $1\le Q\le 300000$
- $0\le A_i < 2^{30}$
- $T_i\in\{1,2\}$
- 若 $T_i=1$：$1\le X_i\le N$ 且 $0\le Y_i<2^{30}$
- 若 $T_i=2$：$1\le X_i\le Y_i\le N$
## 样例解释
开始时 $数组A=[1,2,3]$（下标从 $1$ 开始）。
1) 查询 $2\ 1\ 3$：计算
$A[1]\oplus A[2]\oplus A[3]=1\oplus 2\oplus 3=0$，所以输出 $0$。
2) 查询 $2\ 2\ 3$：计算
$A[2]\oplus A[3]=2\oplus 3=1$，所以输出 $1$。
3) 操作 $1\ 2\ 3$：更新
$A[2]\leftarrow A[2]\oplus 3=2\oplus 3=1$，此时 $数组A=[1,1,3]$。
4) 查询 $2\ 2\ 3$：计算
$A[2]\oplus A[3]=1\oplus 3=2$，所以输出 $2$。
- $1\le N\le 300000$
- $1\le Q\le 300000$
- $0\le A_i < 2^{30}$
- $T_i\in\{1,2\}$
- 若 $T_i=1$：$1\le X_i\le N$ 且 $0\le Y_i<2^{30}$
- 若 $T_i=2$：$1\le X_i\le Y_i\le N$
## 样例解释
开始时 $数组A=[1,2,3]$（下标从 $1$ 开始）。
1) 查询 $2\ 1\ 3$：计算
$A[1]\oplus A[2]\oplus A[3]=1\oplus 2\oplus 3=0$，所以输出 $0$。
2) 查询 $2\ 2\ 3$：计算
$A[2]\oplus A[3]=2\oplus 3=1$，所以输出 $1$。
3) 操作 $1\ 2\ 3$：更新
$A[2]\leftarrow A[2]\oplus 3=2\oplus 3=1$，此时 $数组A=[1,1,3]$。
4) 查询 $2\ 2\ 3$：计算
$A[2]\oplus A[3]=1\oplus 3=2$，所以输出 $2$。