No.3423 Minimum Xor Query
問題文最終更新日: 2026-01-12 11:30:22
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
まみめ
kidodesu