用trie树解决最大异或对问题（On）

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N = 1e5+10;
 6 const int M = 300e4+10;
 7 int arr[N];
 8 int son[M][2];
 9 int flag[M], idx;
10 
11 void insert(int x){
12     int k = 30;
13     int p = 0;
14     while(k >= 0){
15         int tmp = x >> k & 1;
16         if(!son[p][tmp]) son[p][tmp] = ++idx;
17         p = son[p][tmp];
18         --k;
19     }
20     flag[p]++;
21 }
22 int main(){
23     int res = 0;
24     int n;
25     cin >> n;
26     for(int i = 0;i < n;++i){
27         cin >> arr[i];
28         insert(arr[i]);
29     }
30     for(int i = 0;i < n;++i){
31         int k = 30;
32         int p = 0;
33         int sum = 0;
34         while(k >= 0){
35             int tmp = arr[i]>>k & 1;
36             if(son[p][!tmp]){
37                  p = son[p][!tmp];
38                  sum += 1 << k;
39             }
40             else p = son[p][tmp];
41             --k;
42         }
43         res = max(res,sum);
44     }
45     cout << res ;
46     return 0;
47 }