AT_abc185_f.[ABC185F] Range Xor Query

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 $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
```
3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3
```
输出#1
```
0
1
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 \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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页