Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset stl+位运算解法

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

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

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

Multiset is a set, where equal elements are allowed.

Input

The first line of the input contains a single integer q (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 set A.

Output

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

Example

Input

10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11

Output

Note

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

The answer for the sixth query is integer $\text{[math]}$ — maximum among integers $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ .

题目大意：给一定操作，（1）增加一个数x，（2）删除一个数x，（3）询问在该multiset的数中与x异或的最大值

个人感悟：看了多种做法，有用字典树的，还有直接用stl Multiset用位运算模拟，相比之下我觉得后者过程更简洁，但更难理解些。

题目解析：下面将提供后者的做法及解释，如果有讲的错误和不懂的地方，欢迎在下方评论

假设x的二进制形式为0000 1000(8)，那么要想取得最大值，则y应该与x的二进制形式相反才可以，如0111 0111(119)， x^y = 0111 1111(127)

所以我们尽可能使y的二进制形式与x对应0位置从左到右存在1，（可能有点拗口）继续以x的二进制形式为0000 1000(8)，如果存在0100 0000（64）， 0011 1111（63）这两个数，我们肯定会选64，就是这个从左向右选择1的道理

那么我们怎么判断最高为是否为1呢，我们可以用（1 << i）表示最高位为1, （注 i : 29 -> 0）然后 ~x&（1 << i）就可以得到最高位了。最后再用个数ans记录当前能取到的最大值

ans = ans | (~x&（1 << i）), 判断这个ans是否在multimap中，如果不存在就返回到之前的ans， ans = ans ^ (1 << i)

接下来就讲一下STLmultimap 的一些简单函数

首先要定义multimap : multimap<int>ms;

增加一个数: ms.insert(x);
删除所有键值为x的数:ms.earse(x)

删除一个数:ms.earse(ms.find(x))

二分查找：ms.lower_bound(x);

注：multimap中的数按照从小到大排序

然后可以贴代码了

#include <iostream>
#include <set>
#include <cstdio>
using namespace std;
multiset<int>s;
int main()
{
    ios::sync_with_stdio(false);
    int n, x;
    char op;
    cin >> n;
    s.insert(0);
    while(n--){
        cin >> op >> x;
        if(op == '+'){
            s.insert(x);//添加一个数
        }else if(op == '-'){
            s.erase(s.find(x));//删除一个数
        }else if(op == '?'){
            int ans = 0;
            for(int i = 29; i >= 0; i--){
                ans |= (~x&(1 << i));//求出最高位的数，然后不断往下搜
                auto it  = s.lower_bound(ans);//二分搜索， 得到一个
                if(it == s.end() || *it >= ans + (1 << i)){//没有搜到， 第一个是搜到末尾了，第二个是搜到了一个大于ans的数，具体可以查阅lower_bound函数
                    ans ^= 1<<i;
                }
            }
            x ^= ans;
            cout << x << endl;
        }
    }
    return 0;
}

View Code