F - Range Xor Query Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ 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 のビット単位 xor を表します。

ビット単位 xor とは

整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 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 は 1 または 2
  • T_i = 1 なら 1 \le X_i \le N かつ 0 \le Y_i \lt 2^{30}
  • 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 行に 1 つずつ、順に出力せよ。

入力例 1

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

出力例 1

0
1
2

1 個目のクエリでは 1 \oplus 2 \oplus 3 = 0 を出力します。
2 個目のクエリでは 2 \oplus 3 = 1 を出力します。
3 個目のクエリでは A_2 が 2 \oplus 3 = 1 で置き換えられます。
4 個目のクエリでは 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

Score : 600 points

Problem Statement

We have an integer sequence A of length N.
You will process Q queries on this sequence. In the i-th query, given values T_i, X_i, and Y_i, do the following:

  • If T_i = 1, replace A_{X_i} with A_{X_i} \oplus Y_i.
  • If T_i = 2, print A_{X_i} \oplus A_{X_i + 1} \oplus A_{X_i + 2} \oplus \dots \oplus A_{Y_i}.

Here, a \oplus b denotes the bitwise XOR of a and b.

What is bitwise XOR?

The bitwise XOR of integers A and B, A \oplus B, is defined as follows:

  • When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \oplus 5 = 6. (In base two: 011 \oplus 101 = 110.)

Constraints

  • 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.

Input

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

Output

For each query with T_i = 2 in the order received, print the response in its own line.

Sample Input 1

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

Sample Output 1

0
1
2

In the first query, we print 1 \oplus 2 \oplus 3 = 0.
In the second query, we print 2 \oplus 3 = 1.
In the third query, we replace A_2 with 2 \oplus 3 = 1.
In the fourth query, we print 1 \oplus 3 = 2.

Sample Input 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

Sample Output 2

1
0
5
3
0