题目链接： https://www.jisuanke.com/course/6497/427111 （收费题目可能打不开）

题目描述

给你n个数的序列，让你求一个区间[l,r]，使得区间元素的异或值最大。（n最大1e5）

输入

3
1 2 3

输出

3

思路

1.首先要知道，异或运算也是有类似前缀和的性质的。
2.所以这道题就转换为，给你n个数字，以及0，让你求其中两个数使其异或的值是最大的。
3.对于这个问题，使用字典树，把数字的二进制当成字符串，从高位到低位插入树中。把这n个数字和0都插入完之后，就枚举每个数字，在字典树中搜索一下,从高位尽量不一样的搜索，这样异或出来的结果是最大的，计算一下最大的异或值，更新答案，时间复杂度是O(32n).

代码(不用转字符串的，懒得改了)

#include<bits/stdc++.h>
using namespace std;
const int N=100000+5;
int n,a[N];
int tr[32*N][2],idx;

void ins(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=0;
        if(s[i]=='1') u=1;
        if(tr[p][u]==0) tr[p][u]=++idx;
        p=tr[p][u];
    }
}

string get(int x)
{
    string s;
        for(int j=0;j<=30;j++)
            if(x>>j&1) s+='1';
            else s+='0';
    reverse(s.begin(),s.end());
    return s;
}

int f(string s)
{
    int res=0,p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=0;
        if(s[i]=='1') u=1;
        if(tr[p][u^1]==0) p=tr[p][u];
        else p=tr[p][u^1],res+=1<<(30-i);
    }

    return res;
}

int main()
{
    cin>>n;
    ins(string(31,'0'));
    int x=0;
    for(int i=1;i<=n;i++)
    {
        int y;cin>>y;
        x^=y;
        a[i]=x;
        string s=get(x);
        ins(s);
    }
    int ans=f(string(31,'0'));
    for(int i=1;i<=n;i++) 
    {
        ans=max(ans,f(get(a[i])));
    }
    cout<<ans<<endl;
    return 0;
}