Codeforces Round #367 (Div. 2) DVasiliy's Multiset

 D. Vasiliy's Multiset time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output

Author has gone out of the stories about Vasiliy, so here is just a formal task description.

You are given q queries and a multisetA, initially containing only integer 0. There are three types of queries:

"+ x" — add integerx to multiset A."- x" — erase one occurrence of integerx from multiset A. It's guaranteed that at least onex is present in the multiset A before this query."? x" — you are given integerx and need to compute the value , i.e. the maximum value of bitwise exclusive OR (also know as XOR) of integer x and some integer y from the multisetA.

Multiset is a set, where equal elements are allowed.

Input

The first line of the input contains a single integerq (1 ≤ q ≤ 200 000) — the number of queries Vasiliy has to perform.

Each of the following q lines of the input contains one of three characters '+', '-' or '?' and an integer x_i (1 ≤ x_i ≤ 10⁹). It's guaranteed that there is at least one query of the third type.

Note, that the integer 0 will always be present in the setA.

Output

For each query of the type '?' print one integer — the maximum value of bitwise exclusive OR (XOR) of integerx_i and some integer from the multisetA.

Example Input 10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11 Output 11 10 14 13 Note

After first five operations multiset A contains integers 0, 8, 9, 11, 6 and 1.

The answer for the sixth query is integer  — maximum among integers ,,, and.

题意：一个multiset，三种操作：加元素，减元素（保证在multiset里有这个元素）、给定一个x求在multiset里的一个元素与x异或最大值。

题解： 好像大概有两种解法，一个是写容器multiset（我还没学过这个呢）。二就是写01字典树，我先学了字典树，再学了这个。。。

对于每个数，我们把它拆成2进制，想像字符串一样加进树中，对于给定的x，我们从高位每次贪心的取与它异或为1的路，往下走。

代码：

#include <iostream> #include <unordered_map> using namespace std; unordered_map<int,int> data[30]; void update(int v, int c){ for(int i = 0; i < 30; i++)data[i][v>>i] += c; } int query(int x){ int cur = 0; for(int i = 29; i >= 0; i--){ cur ^= (1<<i) ^ ((1<<i)&x); if(data[i][cur>>i] == 0)cur ^= (1<<i); } return cur ^ x; } int main(){ ios::sync_with_stdio(false); update(0,1); int Q,x; cin >> Q; string op; while(Q--){ cin >> op >> x; if(op == "+")update(x,1); else if(op == "-")update(x,-1); else cout << query(x) << endl; } return 0; }