← 返回题目列表

AtCoder · abc308_g

G. 最小异或对查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一块黑板,你可以在上面写整数。 最初,黑板上没有写任何整数。 给定 Q 查询,按顺序处理。

查询属于以下三种类型之一:

  • 1 x :写一个 黑板上的 x 。

  • 2 x : 擦除 黑板上的 x 。 在给出这个查询时,保证至少有一个 黑板上写着 x 。

  • 3 :打印黑板上写的两个整数的最小可能的按位异或。 在处理该查询时,保证至少有两个整数被写在黑板上。

什么是按位异或? 非负整数的按位异或 A 和 B, A \oplus B定义如下。
  • 当 A \oplus B 以二进制形式写入, 2^k的地方 (k \geq 0)是 1 如果恰好是其中之一 2^k的地点 A 和 B is 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 or c_i = 2,一个整数 另外给出了 x 。

换句话说,每个查询都采用以下三种格式之一。

1 x
2 x
3

输出

打印 q 行,其中 q 是查询数量,使得 c_i=3.

的 j-th (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-st 查询,a 2 。

处理后 2-nd 查询,一个 2 和 黑板上写着 10 。

处理时 3-rd查询,背板上写的两个整数的最小可能按位异或为 2\oplus 10=8.

处理后 4第一个查询,一个 2,一个 3,和 10 。

处理时 5-th 查询,写在背板上的两个整数的最小可能的按位异或为 2\oplus 3=1.

处理后 6第一个查询,一个 3 和 黑板上写着 10 。

处理时 7-th 查询,写在背板上的两个整数的最小可能的按位异或为 3\oplus 10=9.

处理后 8第一个查询,一个 3 和两个 黑板上写着 10。

处理时 9-th 查询,写在背板上的两个整数的最小可能的按位异或为 10\oplus 10=0.