The XOR Largest Pair(01Trie)

随便说说：
第一次发现字典树还能这样用，以前都是用字典树求一些最简单的'a'-'z'前缀相同的个数,直到看见这道题。。。。才发现数据结构用好了是真的可以无敌。。。

思路：
暴力枚举两个数肯定是超时，那么我们希望有这样一种操作，我们枚举每个数，枚举到当前这个数，我们希望能够在一个很快的时间里(可以是或者)面求出前面与我们当前这个数异或的最大值，这样就相当于所有的数两两都异或了一次，然后我们取一个max就出来了。
所以01trie这个数据结构就可以求出与前面所有数异或最大值。
01trie就是只包含0和1的树，对于所有的数字，我们都可以转化为二进制处理,那么我们可以考虑用01trie存储这些二进制，然后枚举每个数，一边把这些数转成二进制插到字典树上面去，一边与之前插入的二进制比较求最大值。
字典树怎么插入？很简单，看我代码就会。
那么字典树怎么根据当前这个数找到与之前所有数异或的最大值呢？把当前这个数拆成二进制，然后当前这位是0就去看看1有没有，有的话加入答案，没有就算了，继续找。。。大概看代码把(虽然我也是看的别人代码懂的。。。(逃
代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;


typedef long long int ll;
const int maxn = 2e6 + 10;
int trie[maxn][2],tot;
void insert(ll x){
    int p = 0;
    for(int i = 31; i >= 0; i--){
        bool c = (x >> i) & 1;
        if(!trie[p][c])trie[p][c] = ++tot;
        p = trie[p][c];
    }
}
ll query(ll x){
    ll ans = 0;
    int p = 0;
    for(int i = 31; i >= 0; i--){
        bool c = (x >> i) & 1;
        bool o = c ^ 1;
        if(trie[p][o])ans = ans << 1 | 1,p = trie[p][o];
        else ans = ans << 1,p = trie[p][c];
    }
    return ans;
}
void solved(){
    int n;cin>>n;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll x;cin>>x;insert(x);
        ans = max(ans,query(x));
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}