Minimum Xor Pair Query

题目描述

黑板上可以写整数。最初，黑板上没有写任何整数。给定 $Q$ 个查询，按顺序处理它们。 查询有以下三种类型之一：

$1 x$ ：在黑板上写下一个 $x$。

$2 x$ ：从黑板上擦去一个 $x$。在给出该查询时，保证黑板上至少写有一个 $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$ 个此类查询的答案。

9
1 2
1 10
3
1 3
3
2 2
3
1 10
3

8
1
9
0

提示

$1\leq Q \leq 3\times 10^5$ 0\leq x < 2 ^{30} 当给出查询 $2$ 时，黑板上至少写有一个 $x$。 当给出查询 $3$ 时，黑板上至少写有两个整数。 所有输入值均为整数。处理第 $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$.

标签: AtCoder|abc308G

来源

AtCoder|abc308G