103086: [Atcoder]ABC308 G - Minimum Xor Pair Query
Description
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.
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 1
9 1 2 1 10 3 1 3 3 2 2 3 1 10 3
Sample Output 1
8 1 9 0
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$.
Input
题意翻译
### 题目描述 这里有一块你可以写整数的黑板，初始黑板上什么都没有。 现在有 $q$ 个操作/询问，格式如下： + 操作 `1 x`：在黑板上写下一个数 $x$。 + 操作 `2 x`：将**一个**整数 $x$ 从黑板上擦去，保证此时黑板上至少有一个整数 $x$。 + 询问 `3`：输出黑板上任意两个整数的异或值的最小值，保证此时黑板上至少有两个数。 ### 输入格式 第一行一个整数 $q$，表示操作/询问总数。 接下来 $q$ 行，每行一个操作，格式如上。 ### 输出格式 对于每个询问 `3`，输出黑板上任意两个整数的异或值的最小值。 ### 数据范围 $1\leq q\leq 3\times 10^5,0\leq x<2^{30}$。 ### 样例说明 **对于样例 1：** 共有 9 个询问。 1. 此时黑板上有整数 $\{2\}$。 2. 此时黑板上有整数 $\{2,10\}$。 3. $2\oplus10=8$ 是黑板上最小的异或值。 4. 此时黑板上有整数 $\{2,3,10\}$。 5. $2\oplus3=1$ 是黑板上最小的异或值。 6. 此时黑板上有整数 $\{3,10\}$。 7. $3\oplus10=9$ 是黑板上最小的异或值。 8. 此时黑板上有整数 $\{3,10,10\}$。 9. $10\oplus10=0$ 是黑板上最小的异或值。 Translate by Ew_Cors.Output
分数：$600$分
问题描述
有一个黑板，你可以在上面写整数。最初，黑板上没有写任何整数。给定$Q$个查询，按顺序处理它们。
查询可能有以下三种类型之一：
-
1 x：在黑板上写下一个$x$。 -
2 x：从黑板上擦除一个$x$。在给出此查询时，保证黑板上至少写了一个$x$。 -
3：打印黑板上两个整数的最小可能按位异或。在处理此查询时，保证黑板上至少写有两个整数。
什么是按位异或？
非负整数$A$和$B$的按位异或$A \oplus B$定义如下。- 当$A \oplus B$用二进制表示时，$2^k$s位（$k \geq 0$）为$1$，如果$A$和$B$的$2^k$s位中恰好有一个为$1$，否则为$0$。
限制条件
- $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$。
换句话说，每个查询可能有以下三种格式之一。
$1$ $x$
$2$ $x$
$3$
输出
打印$q$行，其中$q$是查询数，满足$c_i=3$。
第$j$行（$1\leq j\leq q$）应包含第$j$个这样的查询的答案。
样例输入 1
9 1 2 1 10 3 1 3 3 2 2 3 1 10 3
样例输出 1
8 1 9 0
在处理第$1$个查询后，黑板上写了一个$2$。
在处理第$2$个查询后，黑板上写了一个$2$和一个$10$。
在处理第$3$个查询时，黑板上写的两个整数的最小可能按位异或为$2\oplus 10=8$。
在处理第$4$个查询后，黑板上写了一个$2$，一个$3$和一个$10$。
在处理第$5$个查询时，黑板上写的两个整数的最小可能按位异或为$2\oplus 3=1$。
在处理第$6$个查询后，黑板上写了一个$3$和一个$10$。
在处理第$7$个查询时，黑板上写的两个整数的最小可能按位异或为$3\oplus 10=9$。
在处理第$8$个查询后，黑板上写了一个$3$和两个$10$。
在处理第$9$个查询时，黑板上写的两个整数的最小可能按位异或为$10\oplus 10=0$。