CODEFORCES ROUND #367 (DIV. 2) D
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
inline int max(int a, int b) { return (a > b ? a : b); }
struct Node
{
int size;
Node *ch[2], *fa;
Node() { fa = ch[0] = ch[1] = 0, size = 0; }
};
typedef Node *lpNode;
struct Trie
{
lpNode root;
Trie() : root(new Node()) {}
void insert(int x)
{
lpNode cur = root;
cur->size++;
for (int i = 31; i >= 0; i--)
{
int id = (x >> i) & 1;
if (cur->ch[id] == 0)
cur->ch[id] = new Node(), cur->ch[id]->fa = cur;
cur = cur->ch[id];
cur->size++;
}
}
void remove(int x)
{
lpNode cur = root;
cur->size--;
for (int i = 31; i >= 0; i--)
{
cur = cur->ch[(x >> i) & 1];
cur->size--;
}
while (cur->fa != 0 && cur->size == 0)
cur->fa->ch[cur == cur->fa->ch[1]] = 0, cur = cur->fa;
}
int query(int x)
{
x = ~x;
int ans = 0;
lpNode p = root;
for (int i = 31; i >= 0; i--)
{
ans <<= 1;
if ((x >> i) & 1 && p)
if (p->ch[1])
p = p->ch[1], ans++;
else
p = p->ch[0];
else if (p->ch[0])
p = p->ch[0];
else
p = p->ch[1], ans++;
}
return ans;
}
};
int main()
{
int q, tmp;
char ch;
Trie t;
t.insert(0);
scanf("%d", &q);
for (int i = 0; i < q; i++)
{
ch = getchar();
while (ch != '+' && ch != '-' && ch != '?') ch = getchar();
scanf("%d", &tmp);
if (ch == '+')
t.insert(tmp);
else if (ch == '-')
t.remove(tmp);
else if (ch == '?')
printf("%d\n", t.query(tmp) ^ tmp);
}
return 0;
}