seuOJ191 - 垃圾可重集

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：4000 ms
• 空间限制：256 MiB
• 题目标签：短码, 2019

题目描述

4qwerty7 了解到了 PB_DS 库，想要来考考你：

有一个初始为空的可重复元素集合，有三种操作：

1. 删除一个数

2. 增加一个数

3. 询问第 $x$ 小数

请实现它。

参考资料：https://www.luogu.org/blog/Chanis/gnu-pbds。

输入格式

第一行一个数 $n(1\leq n \leq 10^6)$表示操作数。

下面 $n$ 行每行描述一个操作。

• I x 表示加入一个数 $x$
• D x 表示删除一个等于 $x$ 的数字（保证存在，如果存在多个只删除一个）
• K x 询问第 $x$ 小的数字是多少

输入数据中的 $x$ 与 $lastans$ 异或方为真实值，$lastans$ 为最近一次输出的答案，没有输出时为 $0$。

所有 $x$ 的真实值满足 $0\leq x \leq 10^9$。

输出格式

对于每个 K 操作输出一行一个数字表示答案。

样例

输入样例

6
I 1
I 2
I 3
K 3
D 1
K 1

输出样例

3
3