G - Minimum Xor Pair Query

Contest Duration: 2023-07-01(Sat) 12:00 - 2023-07-01(Sat) 13:40 (local time) (100 minutes) Back to Home

G - Minimum Xor Pair Query Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

整数を書くことができる黒板があります。はじめ黒板には整数は何も書かれていません。クエリが $Q$ 個与えられるので順に処理してください。

クエリは以下の $3$ 種類です。

1 x : 黒板に $x$ を一つ書き込む。
2 x : 黒板に書かれた $x$ を一つ消去する。このクエリが与えられるとき、黒板に $x$ が一つ以上書かれていることが保証される。
3 : 黒板に書かれた二つの整数のビット単位 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\leq Q \leq 3\times 10^5$
$0\leq x < 2 ^{30}$
クエリ $2$ が与えられるとき、黒板に $x$ が一つ以上書かれている
クエリ $3$ が与えられるとき、黒板に整数が二つ以上書かれている
入力される数値は全て整数

入力

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

 $Q$ 
 $\mathrm{query}_1$ 
 $\mathrm{query}_2$ 
 $\vdots$ 
 $\mathrm{query}_Q$

$i$ 番目のクエリ $\mathrm{query}_i$ では、まずクエリの種類 $c_i$ （ $1, 2, 3$ のいずれか）が与えられる。 $c_i = 1, c_i = 2$ の場合はさらに整数 $x$ が追加で与えられる。

すなわち、各クエリは以下に示す $3$ つの形式のいずれかである。

 $1$   $x$

 $2$   $x$

$3$

出力

$c_i=3$ を満たすクエリの回数を $q$ として $q$ 行出力せよ。

$j\ (1\leq j\leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$1$ 番目のクエリ処理後、黒板には $2$ が一つ書かれています。

$2$ 番目のクエリ処理後、黒板には $2,10$ が一つずつ書かれています。

$3$ 番目のクエリ処理時、黒板に書かれた二つの数のビット単位 XOR として考えられる最小値は $2\oplus 10=8$ です。

$4$ 番目のクエリ処理後、黒板には $2,3,10$ が一つずつ書かれています。

$5$ 番目のクエリ処理時、黒板に書かれた二つの数のビット単位 XOR として考えられる最小値は $2\oplus 3=1$ です。

$6$ 番目のクエリ処理後、黒板には $3,10$ が一つずつ書かれています。

$7$ 番目のクエリ処理時、黒板に書かれた二つの数のビット単位 XOR として考えられる最小値は $3\oplus 10=9$ です。

$8$ 番目のクエリ処理後、黒板には $3$ が一つ、 $10$ が二つ書かれています。

$9$ 番目のクエリ処理時、黒板に書かれた二つの数のビット単位 XOR として考えられる最小値は $10\oplus 10=0$ です。

Score : $600$ points

Problem Statement

There is a blackboard on which you can write integers. Initially, no integer is written on the blackboard. Given $Q$ queries, process them in order.

The query is of one of the following three kinds:

1 x : write an $x$ on the blackboard.
2 x : erase an $x$ from the blackboard. At the point this query is given, it is guaranteed that at least one $x$ is written on the blackboard.
3 : print the minimum possible bitwise XOR of two of the integers written on the blackboard. At the point this query is processed, it is guaranteed that at least two integers are written on the blackboard.

What is bitwise XOR?

The bitwise XOR of non-negative integers $A$ and $B$ , $A \oplus B$ , is defined as follows.

When $A \oplus B$ is written in binary, the $2^k$ s place ( $k \geq 0$ ) is $1$ if exactly one of the $2^k$ s places of $A$ and $B$ is $1$ , and $0$ otherwise.

For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$ ).

Constraints

$1\leq Q \leq 3\times 10^5$
$0\leq x < 2 ^{30}$
When a query $2$ is given, at least one $x$ is written on the blackboard.
When a query $3$ is given, at least two integers are written on the blackboard.
All input values are integers.

Input

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

 $Q$ 
 $\mathrm{query}_1$ 
 $\mathrm{query}_2$ 
 $\vdots$ 
 $\mathrm{query}_Q$

In the $i$ -th query, $\mathrm{query}_i$ , the kind of query, $c_i$ (one of $1$ , $2$ , or $3$ ), is first given. If $c_i = 1$ or $c_i = 2$ , an integer $x$ is additionally given.

In other words, each query is in one of the following three formats.

 $1$   $x$

 $2$   $x$

$3$

Output

Print $q$ lines, where $q$ is the number of queries such that $c_i=3$ .

The $j$ -th $(1\leq j\leq q)$ line should contain the answer to the $j$ -th such query.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

After processing the $1$ -st query, a $2$ is written on the blackboard.

After processing the $2$ -nd query, a $2$ and a $10$ are written on the blackboard.

When processing the $3$ -rd query, the minimum possible bitwise XOR of two of the integers written on the backboard is $2\oplus 10=8$ .

After processing the $4$ -th query, a $2$ , a $3$ , and a $10$ are written on the blackboard.

When processing the $5$ -th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $2\oplus 3=1$ .

After processing the $6$ -th query, a $3$ and a $10$ are written on the blackboard.

When processing the $7$ -th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $3\oplus 10=9$ .

After processing the $8$ -th query, a $3$ and two $10$ s are written on the blackboard.

When processing the $9$ -th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $10\oplus 10=0$ .