Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset（01字典树求最大异或值）

http://codeforces.com/contest/706/problem/D

题意：
有多种操作，操作1为在字典中加入x这个数，操作2为从字典中删除x这个数，操作3为从字典中找出一个数使得与给定的数的异或值最大。

思路：

因为这道题目涉及到删除操作，所以用一个变量cnt来记录前缀的数量，加入时就+1，删除时就减1。查询时前缀数量>0时就说明是存在的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 200000 + 5;
 6 typedef long long ll;
 7 int num = 0;
 8 
 9 struct Trie
10 {
11     int son[2];
12     int cnt;
13 }t[32*maxn];
14 
15 void init(int x)
16 {
17     t[x].cnt = 0;
18     memset(t[x].son,0,sizeof(t[x].son));
19 }
20 
21 void insert(ll x)
22 {
23     int u = 0;
24     for(int i=32;i>=0;i--)
25     {
26         int c = ((x>>i)&1);
27         if(!t[u].son[c])
28         {
29             num++;
30             init(num);
31             t[u].son[c] = num;
32         }
33         u = t[u].son[c];
34         t[u].cnt++;
35     }
36 }
37 
38 void del(ll x)
39 {
40     int u = 0;
41     for(int i=32;i>=0;i--)
42     {
43         int c = ((x>>i)&1);
44         u = t[u].son[c];
45         t[u].cnt--;
46     }
47 }
48 
49 ll query(ll x)
50 {
51     ll ans = 0;
52     int u = 0;
53     for(int i=32;i>=0;i--)
54     {
55         int c = ((x>>i)&1);
56         if(t[u].son[c^1] && t[t[u].son[c^1]].cnt)
57         {
58             ans+=(1<<i);
59             u = t[u].son[c^1];
60         }
61         else u = t[u].son[c];
62     }
63     return ans;
64 }
65 
66 int main()
67 {
68     //freopen("in.txt","r",stdin);
69     int n;
70     scanf("%d",&n);
71     insert(0);
72     while(n--)
73     {
74         char op[2]; ll x;
75         scanf("%s%lld",op,&x);
76         if(op[0]=='+') insert(x);
77         else if(op[0]=='-')  del(x);
78         else if(op[0]=='?')  printf("%lld
",query(x));
79     }
80     return 0;
81 }