M - NAND Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

0 以上 2^{30} 未満の整数 a,b に対して、a と b の NAND を次のように定めます。

  • a,b をそれぞれ、必要に応じて先頭に 0 を補って 2 進法 30 桁で表します。各桁について、両方の数のその桁が 1 ならば 0、そうでなければ 1 とすると、 2 進法 30 桁で表された整数が得られます。それを a と b の NAND とします。

0 以上 2^{30} 未満の整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 p x：A_p を 0 以上 2^{30} 未満の整数 x に変更する。
  • 2 l r：B_l=A_l とし、i=l+1,l+2,\ldots,r の順に B_i を B_{i-1} と A_i の NAND として定める。B_r を出力する。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \lt 2^{30}
  • 1 種類目のクエリについて、1 \leq p \leq N, 0 \leq x \lt 2^{30}
  • 2 種類目のクエリについて、1 \leq l \leq r \leq N
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 p x

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

4 3
5 3 12 10
2 1 4
2 2 3
2 3 3

出力例 1

1073741821
1073741823
12

1 番目のクエリでは、以下のように答えを計算できます。

  1. B_1=A_1=5 です。
  2. B_1 (=5) と A_2 (=3) の NAND は 1073741822 なので、 B_2=1073741822 です。
  3. B_2 (=1073741822) と A_3 (=12) の NAND は 1073741811 なので、 B_3=1073741811 です。
  4. B_3 (=1073741811) と A_4 (=10) の NAND は 1073741821 なので、 B_4=1073741821 です。この値を出力します。

入力例 2

5 6
7 10 12 3 5
2 2 4
1 3 6
2 1 5
2 3 3
1 1 1073741823
2 1 2

出力例 2

1073741820
1073741819
6
1073741813

入力例 3

3 5
1073741823 0 536870912
2 1 2
2 1 3
1 2 1073741823
2 1 3
2 2 2

出力例 3

1073741823
536870911
1073741823
1073741823

Score: 4 points

Problem Statement

For integers a,b that are at least 0 and less than 2^{30}, define the NAND of a and b as follows:

  • Represent each of a,b using 30 digits in base 2, adding leading 0s if necessary. For each digit, set the resulting digit to 0 if the corresponding digits of both numbers are 1, and to 1 otherwise. This gives an integer represented by 30 digits in base 2. This integer is the NAND of a and b.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of integers that are at least 0 and less than 2^{30}.

Process Q queries. Each query is of one of the following 2 types:

  • 1 p x: Change A_p to the integer x, which is at least 0 and less than 2^{30}.
  • 2 l r: Set B_l=A_l, and then, for i=l+1,l+2,\ldots,r in this order, define B_i as the NAND of B_{i-1} and A_i. Print B_r.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \lt 2^{30}
  • For type 1 queries, 1 \leq p \leq N, 0 \leq x \lt 2^{30}
  • For type 2 queries, 1 \leq l \leq r \leq N
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 p x

2 l r

Output

Let q be the number of type 2 queries. Print q lines. The j-th line should contain the answer to the j-th type 2 query.

Sample Input 1

4 3
5 3 12 10
2 1 4
2 2 3
2 3 3

Sample Output 1

1073741821
1073741823
12

For query 1, the answer can be calculated as follows:

  1. B_1=A_1=5.
  2. The NAND of B_1 (=5) and A_2 (=3) is 1073741822, so B_2=1073741822.
  3. The NAND of B_2 (=1073741822) and A_3 (=12) is 1073741811, so B_3=1073741811.
  4. The NAND of B_3 (=1073741811) and A_4 (=10) is 1073741821, so B_4=1073741821. Print this value.

Sample Input 2

5 6
7 10 12 3 5
2 2 4
1 3 6
2 1 5
2 3 3
1 1 1073741823
2 1 2

Sample Output 2

1073741820
1073741819
6
1073741813

Sample Input 3

3 5
1073741823 0 536870912
2 1 2
2 1 3
1 2 1073741823
2 1 3
2 2 2

Sample Output 3

1073741823
536870911
1073741823
1073741823