問題一覧 > 通常問題

No.3423 Minimum Xor Query

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 16
作問者 : syndrome / テスター : harel まみめ hirayuu_yc rogi52 👑 qand kidodesu 👑 ArcAki Eku
お気に入りにしたユーザー ProblemId : 12889 / 自分の提出
問題文最終更新日: 2026-01-12 11:30:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest YNUCPC Contest 2 (順位表) の他の問題:

The time limit is set strictly!!

Problem Statement

You are given a sequence of non-negative integers $A = (A_1,A_2, \dots,A_N)$ of length $N$.

Process $Q$ queries in order. There are $2$ types of queries, each given in one of the following formats.

  • $1$ $i$ $x$ : Replace $A_i$ with $x$.
  • $2$ $r$ : Output $\min_{1 \leq i < j \leq r}$ $A_i$ $\oplus$ $A_j$. Here, $\oplus$ denotes bitwise XOR.

Input

  • $2 \leq N \leq 2 \times 10^4$
  • $1 \leq Q \leq 5 \times 10^4$
  • $0 \leq A_i < 2^{20} (1 \leq i \leq N)$
  • For queries of the first format, $1 \leq i \leq N, 0 \leq x < 2^{20}$
  • For queries of the second format, $2 \leq r \leq N$
  • There is at least one query of the second format
  • All input values are integers

The input is given from standard input in the following format.

$N\;Q$
$A_1\;A_2\;...\;A_N$  
$query_1$
$query_2$
$⋮$
$query_Q$

Each query is given in one of the following $2$ formats.

$1\;i\;x$
$2\;r$

Output

If there are $K$ queries of the $2$nd type, output $K$ lines.

On the $i$-th line ($1 \leq i \leq K$), output the answer to the $i$-th query of the $2$nd type.

Sample

Sample 1
Input
5 4
0 8 16 24 32
2 5
1 3 8
2 5
2 2
Output
8
0
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。