今天可爱的Mayuyu会带领大家来学习一个东西，那就是异或最大，Mayuyu的问题描述如下。

题目：给定一个数组a[]，再给出m个询问，每个询问一个数x，在a[]中找出一个数y，使得x与y的异或值最大。

分析：最直观的思路就是对于每一个询问，直接暴力在数组a[]中比较，找最大的，但这样做的时间复杂度会很大。

     我们有一个很好的解法，那就是字典树，假设所有的数字范围均在int内，那么就可以建立深度为32的字典树

     即可，所以总的时间复杂度为O(32*m)。

     建好字典树后，从根节点往下遍历一遍就行了，先对x按位取反，尽量走相同的节点，如果不存在就忽略。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

class Trie
{
    public:
    Trie *next[2];
    Trie()
    {
        memset(next,NULL,sizeof(next));
    }
};

Trie *root;

void Insert(LL n)
{
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        int id = (n >> i) & 1;
        if(p->next[id] == NULL)
             p->next[id] = new Trie();
        p = p->next[id];
    }
}

void Delete(Trie *T)
{
    if(T == NULL) return;
    for(int i=0;i<2;i++)
        if(T->next[i] != NULL)
            Delete(T->next[i]);
}

LL Match(LL m)
{
    m = ~m;
    LL ans = 0;
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        ans <<= 1;
        int bit = (m >> i) & 1;
        if(bit)
        {
            if(p->next[1])
            {
                p = p->next[1];
                ans++;
            }
            else
            {
                p = p->next[0];
            }
        }
        else
        {
            if(p->next[0])
            {
                p = p->next[0];
            }
            else
            {
                p = p->next[1];
                ans++;
            }
        }
    }
    return ans;
}

int main()
{
    int T, tt = 1;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        root = new Trie();
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            LL val;
            scanf("%I64d",&val);
            Insert(val);
        }
        printf("Case #%d:\n",tt++);
        while(m--)
        {
            LL val;
            scanf("%I64d",&val);
            printf("%I64d\n",Match(val));
        }
        Delete(root);
    }
    return 0;
}

题目：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1216

题意：给定一个数组，在这个数组中找出两个数，使它们的异或值最大。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 100005;
typedef long long LL;
const LL INF = (LL)1<<61;

int a[N];

class Trie
{
    public:
    Trie *next[2];
    Trie()
    {
        memset(next,NULL,sizeof(next));
    }
};

Trie *root;

void Insert(LL n)
{
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        int id = (n >> i) & 1;
        if(p->next[id] == NULL)
             p->next[id] = new Trie();
        p = p->next[id];
    }
}

void Delete(Trie *T)
{
    if(T == NULL) return;
    for(int i=0;i<2;i++)
        if(T->next[i] != NULL)
            Delete(T->next[i]);
}

LL Match(LL m)
{
    m = ~m;
    LL ans = 0;
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        ans <<= 1;
        int bit = (m >> i) & 1;
        if(bit)
        {
            if(p->next[1])
            {
                p = p->next[1];
                ans++;
            }
            else
            {
                p = p->next[0];
            }
        }
        else
        {
            if(p->next[0])
            {
                p = p->next[0];
                ans++;
            }
            else
            {
                p = p->next[1];
            }
        }
    }
    return ans;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        root = new Trie();
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            Insert(a[i]);
        }
        LL ans = -INF;
        for(int i=0;i<n;i++)
            ans = max(ans,Match(a[i]));
        printf("%lld\n",ans);
        Delete(root);
    }
    return 0;
}

题目：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1717

题意：给定一个数组a[]，在这个数组中选择一个前缀和一个后缀，使它们的异或值最大，前缀与后缀不能交叉。

分析：Mayuyu明白一点，两个相同值异或后为0，那么所以以1 2 4 8 16为例说明，1 2 4 8是a[]的一个前缀

     而4 8 16是a[]的一个后缀，但是它们有交叉，由异或的性质，它们实际上与前缀1 2和后缀16等价，因为

     中间的相同部分抵消了。这样我们先对所有前缀插入深度为40的字典树，然后对于每一个后缀来查找，求出

     最大值即可。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 100005;
typedef long long LL;
const LL INF = (LL)1<<61;

LL a[N];

class Trie
{
    public:
    Trie *next[2];
    Trie()
    {
        memset(next,NULL,sizeof(next));
    }
};

Trie *root;

void Insert(LL n)
{
    Trie *p = root;
    for(int i=40;i>=0;i--)
    {
        int id = (n >> i) & 1;
        if(p->next[id] == NULL)
             p->next[id] = new Trie();
        p = p->next[id];
    }
}

void Delete(Trie *T)
{
    if(T == NULL) return;
    for(int i=0;i<2;i++)
        if(T->next[i] != NULL)
            Delete(T->next[i]);
}

LL Match(LL m)
{
    m = ~m;
    LL ans = 0;
    Trie *p = root;
    for(int i=40;i>=0;i--)
    {
        ans <<= 1;
        int bit = (m >> i) & 1;
        if(bit)
        {
            if(p->next[1])
            {
                p = p->next[1];
                ans++;
            }
            else
            {
                p = p->next[0];
            }
        }
        else
        {
            if(p->next[0])
            {
                p = p->next[0];
                ans++;
            }
            else
            {
                p = p->next[1];
            }
        }
    }
    return ans;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        root = new Trie();
        LL tmp = 0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            tmp ^= a[i];
            Insert(tmp);
        }
        tmp = 0;
        LL ans = -INF;
        for(int i=0;i<n;i++)
        {
            tmp ^= a[n-1-i];
            ans = max(ans,Match(tmp));
        }
        printf("%lld\n",ans);
        Delete(root);
    }
    return 0;
}