E - Do Not Use Segment Tree
Earlgray
2
s
1024
MB
500
点
問題文
長さ $N$ の整数列 $A$ が与えられます。$Q$ 個のクエリを処理してください。
各クエリでは、 $t,l,r,x$ が与えられます。クエリの内容は以下の通りです。
- $t = 0$ のとき : $l$ 以上 $r$ 以下の全ての整数 $i$ について、 $A_i$ を $A_i \text{ xor } x$ に更新する。
- $t = 1$ のとき : $\displaystyle\max_{l \le i \le r}A_i$ を出力する。ただし、このクエリは $50$ 回までしか与えられない。
Python には定数倍がきついかもしれないので、注意してください。
制約
- 入力は全て整数
- $1 \le N \le 10^5$
- $0 \le A_i < 2^{32}$
- $1 \le Q \le 10^5$
- $0 \le t \le 1$
- $1 \le l \le r \le N$
- $0 \le x < 2^{32}$
- $t = 1$ ならば $x = 0$
- $\sum t \le 50$
入力
$N$
$A_1$ $\dots$ $A_N$
$Q$
$t_1$ $l_1$ $r_1$ $x_1$
$\vdots$
$t_Q$ $l_Q$ $r_Q$ $x_Q$
出力
$t = 1$ のクエリごとに、答えを改行区切りで出力せよ。
入力例 1
6
1 2 3 4 5 6
10
1 2 5 0
0 1 4 7
1 1 1 0
1 2 3 0
0 5 6 4
1 1 5 0
0 1 3 1
0 5 5 5
1 2 6 0
1 1 2 0
出力例 1
5
6
5
6
5
7
はじめ、 $A=[1, 2, 3, 4, 5, 6]$ です。
クエリは以下のように処理されます。
クエリ $1$ : $\max([2, 3, 4, 5])=5$
クエリ $2$ : $[1, 2, 3, 4, 5, 6] \rightarrow [6, 5, 4, 3, 5, 6]$
クエリ $3$ : $\max([6])=6$
クエリ $4$ : $\max([5, 4])=5$
クエリ $5$ : $[6, 5, 4, 3, 5, 6] \rightarrow [6, 5, 4, 3, 1, 2]$
クエリ $6$ : $\max([6, 5, 4, 3, 5])=6$