输入样例
5
1
0
5
4
2
输出样例
6 4 5
刚开始看到这个题，我是毫无思绪，看了一下题解：
https://www.acwing.com/video/2339/
老师说这个是最大异或对的变形
于是我去找了一下最大异或对
看完之后我只能想到暴力解决，然后看了样例10^5，我就知道是行不通的，但是确实想不到好一点的办法。
老规矩，看了视频之后。
https://www.acwing.com/problem/content/video/145/
我从老师了解到一个trie串写法好像是用二维数组实现把每一个元素存在一个二维数组中。
核心关键（一个节点的所有子孙都有相同的前缀）
代码就由此而来
#include<iostream>
#include<algorithm>
using namespace std;
const int N=31*1e5+10;//因为数据的范围是2的31次方所以二进制有31位
int trie[N][2];//用二维数组把每一个数二进制每一位存储下来
int idx;//用idx来给未分配的标记
void get(int x)
{
int p=0;
for(int i=30;i>=0;i--)
{
int s=x >> i & 1;//x二进制第i位表示的数字
if(!trie[p][s]) trie[p][s]=++idx;//把他放到trie保存
//保存方式，trie[p][s]里面放着是子节点的下标，真正存放**x二进制第i位表示的数字**的是列下标
p=trie[p][s];//转移到子节点
}
}
int f(int y)//寻找与他异或和最大的数
{
int p=0,res=0;
for(int i=30;i>=0;i--)
{
int s=y>>i&1;
if(trie[p][!s]) {res=res*2+!s;p=trie[p][!s];}
else
{
res=res*2+s;p=trie[p][s];//秦九昭算法 res=res*进制+n(从高位到低位每一位对应的数)
}
}
return res;
}
int main(void)
{
int n,t,cot=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
get(t);
int zj=f(t);
cot=max(cot,zj^t);
}
cout<<cot;
}
做完最大异或对，我还是没有搞很清楚这是怎么做牛异或。当老师说从i-j的异或等于Sj^Si-1我就有点懵逼了
然后我自己证明了一下结果有了思路，把他变成类似于一个前缀和的形式，然后把他同最大异或对的思路来做就可以了。
然后我们发现这可以转换为前缀和中找最大异或和，于是代码如下
#include<iostream>
#include<algorithm>
using namespace std;
const int N=21*(1e5+10);
int trie[N][2],g[100010];
int id[N],idx;
void insert(int x,int d)//这些操作和求最大异或和一致
{
int p=0;
for(int i=20;i>=0;i--)
{
int s=x>>i&1;
if(!trie[p][s]) trie[p][s]=++idx;
p=trie[p][s];
}
id[p]=d;
}
int quiry(int y)
{
int p=0;
for(int i=20;i>=0;i--)
{
int s=y>>i&1;
if(trie[p][!s]) p=trie[p][!s];
else
p=trie[p][s];
}
return id[p];
}
int main(void)
{
int n,res=-1,l=1,r=1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>g[i];
g[i]^=g[i-1];
}
insert(g[0],0);
//需要注意的细节，要是不填进去的话，如果只有一项，则会找自己也就是本身那么异或为0则不是我
//们想求的答案
for(int i=1;i<=n;i++)
{
int u=quiry(g[i]);
int sum=g[u]^g[i];
if(res<sum) res=sum,l=u+1,r=i;
insert(g[i],i);
}
cout<<res<<" "<<l<<" "<<r;
}