题目描述
农夫约翰在给他的奶牛们喂食时遇到了一个问题。
他共有 N 头奶牛,编号 1∼N。
每次喂食前,这 N 头奶牛会按照 1∼N 的顺序站成一排。
此外,每头奶牛都被分配了一个可能不唯一的整数。
那么所有被分配的整数就形成了一个长度为 N 的整数序列。
请你在该整数序列中找出一个连续的非空子序列,使得子序列中元素的异或和能够最大。
如果存在多个这样的序列,那么选择序列末端整数对应的奶牛编号更小的那个序列。
如果仍然存在多个可选的序列,那么选择长度最短的那个序列。
输入格式
第一行包含整数 N。
第 2∼N+1 行,每行包含一个整数,其中第 i 行的整数表示编号为 i−1 的牛被分配的整数值。
输出格式
输出三个整数,分别表示最大的异或和,所选序列首端整数对应的奶牛编号,所选序列末端整数对应的奶牛编号。
数据范围
1≤N≤105,
分配给奶牛的整数的范围是 [0,221−1]。
样例
5
1
0
5
4
2
对y总代码的一些注释
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=N*25;
int s[N];
int son[M][2],id[M];//son第一维是编号,用这个编号可以获取到下一个节点点的编号,id可以代表这个节点所代表的数据,用节点编号访问
int idx,n;
void insert(int x, int k) //用于插入数据
{
int p = 0; //0是头结点的编号
for (int i = 20; i >= 0; i -- ) //从一个数的最高位开始插入
{
int u = x >> i & 1; //获取那一位的数字
if (!son[p][u]) son[p][u] = ++ idx; //如果节点不存在,就创建出来
p = son[p][u]; //更新p(现在是当前节点的编号)
}
id[p] = k; //到达了尾部,更新这个节点代表的数值(trie数只有到了尾部才有用)
}
int query(int x) //查找
{
int p = 0; //头结点
for (int i = 20; i >= 0; i -- )
{
int u = x >> i & 1; //取数
if (son[p][!u]) p = son[p][!u]; //如果当前异或可以取到最大值,就走这条路线
else p = son[p][u]; //如果当前节点没有最优,就走有的路
}
return id[p]; //返回这个节点代表的值
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) //读入数据,处理前缀和
{
cin>>s[i];
s[i]^=s[i-1];
}
int res=-1,a,b;
for(int i=1;i<=n;i++)//先查找后插入
{
int k=query(s[i]); //查找s[i]的最大异或的数的下标
int t=s[i]^s[k]; // 计算他们的异或结果
if(res<t) res=t,a=k+1,b=i; // 如果这个结果大,就更新res,因为s[i]^s[k]实际上是下标[k+1~i]的s异或,所以 a=k+1,b=i(左右区间)
insert(s[i],i); //插入
}
cout<<res<<" "<<a<<" "<<b<<endl;
return 0;
}