平衡树

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

神奇的cxlove有一颗平衡树,其树之神奇无法用语言来描述 OrzOrz。 这棵树支持3种操作: 1、加入一个数到树中,维护平衡树的合法性; 2、给一个数X,用O(1)的时间求出来树中的数Y使得 Y ^ X 最大(异或操作, Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1) 3、给一个数X,用O(1)的时间求出来树中的数Y使得 Y ^ X 最小(异或操作, Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1) 请你帮忙实现这颗树。 cxlove由于过于牛,有些事情是无法做到的,你能在1s以内通过就好了。 最后补充一句,cxlove是世界冠军!

Input

第一行是数据组数T (T ≤ 100)

对于每组数据,第一行是操作数N (N ≤ 10000)

以下 行,每行一个字符串一个数字,分别代表:

  1. insert X ,加入数 X
  2. qmax X ,求第2种操作的答案
  3. qmin X ,求第3种操作的答案

输入保证不存在空树Query的情况 (1 ≤ X ≤ 1e9)

Output

对于操作 2 , 3 输出相应的答案。

Sample Input

1
4
insert 1
insert 2
qmin 1
qmax 1

Sample Output

0
3

Hint

Huge input and output. Please do not use: 1. cin ans cout of C++ 2. scanner of Java(Maybe BufferedReader is quicker)

Source

buaads

Manager

Information
Solved Number111
Submit Number323
Problem Tags
constructive algorithms
data structures
trees
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel