CodeForces 706D Vasiliy's Multiset 【01字典树】

题目大意：

现在要对一个multiset执行q次指令，请你根据指令作出相应操作。共有3种指令类型，分别为”+ x”，”- x”和”? x”，他们的要求依次为：向集合中添加一个元素x、删除集合中的一个元素x和查询集合中现已存在的数与x的异或结果最大值。
注意：multiset是一个允许相同元素存在于集合中的一个容器。初始时集合中有且仅有0这个元素。

解题思路：

全题中最重要的指令就是”? x”这个指令了。异或结果最大，就是分解为二进制后，从高位往低位看，这一位为0时尽量取这一位为1的与他进行异或，为1时同理。到这里就能看出来是很明显的字典树啦。

Mycode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX =200010;

char op;
int q, x;
struct Trie
{
    int nex[MAX * 30][2], pre[MAX * 30], tot;
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
    }
    void add()
    {
        int now = 1;
        for(int i = 30; i >= 0; --i)
        {
            if(nex[now][(x >> i) & 1] == 0)
                nex[now][(x >> i) & 1] = ++tot;
            now = nex[now][(x >> i) & 1];
            ++pre[now];
        }
    }
    void sub()
    {
        int now = 1;
        for(int i = 30; i >= 0; --i)
        {
            now = nex[now][(x >> i) & 1];
            --pre[now];
        }
    }
    int query()
    {
        int now = 1, res = 0;
        for(int i = 30; i >= 0; --i)
        {
            //存在此结点 && 此结点有值
            if(nex[now][((x >> i) & 1) ^ 1] && pre[nex[now][((x >> i) & 1) ^ 1]])
                res += (1 << i), now = nex[now][((x >> i) & 1) ^ 1];
            else
                now = nex[now][(x >> i) & 1];
        }
        return res;
    }
} trie;
int main()
{
    trie.init();
    trie.add();
    scanf("%d", &q);
    while(q--)
    {
        getchar();
        scanf("%c%d", &op, &x);
        if(op == '+')
            trie.add();
        else if(op == '-')
            trie.sub();
        else
            printf("%d\n", trie.query());
    }
    return 0;
}