← 返回题目列表

AtCoder · abc185_f

F. 范围异或查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个整数序列 A 长度 N.
您将处理 Q 查询此序列。在 i第一个查询,给定值 T_i, X_i,和 Y_i,执行以下操作:

  • If T_i = 1,替换 A_{X_i} 与 A_{X_i} \oplus Y_i.
  • If 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,定义如下:

  • 当 A \oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
例如, 3 \oplus 5 = 6。 (在基数二中: 011 \oplus 101 = 110.)

约束

  • 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,那么 1 \le X_i \le N 和 0 \le Y_i \lt 2^{30}.
  • If T_i = 2,那么 1 \le X_i \le Y_i \le N.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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 在收到的订单中,在其自己的行中打印响应。


示例输入 1

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

示例输出 1

0
1
2

在第一个查询中,我们打印 1 \oplus 2 \oplus 3 = 0.
在第二个查询中,我们打印 2 \oplus 3 = 1.
在第三个查询中,我们替换 A_2 与 2 \oplus 3 = 1.
在第四个查询中,我们打印 1 \oplus 3 = 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