AcWing 1414. 牛异或
原题链接
中等
作者:
dran
,
2021-05-11 17:10:49
,
所有人可见
,
阅读 325
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010*21,M=100010;
int n,son[N][2],idx,cnt[N],ll,rr;
int a[M],s[M];
void insert(int x){
int p=0,a=s[x];
for(int i=20;i>=0;i--){
int u=a>>i&1;
if(!son[p][u]) son[p][u]=++idx,p=son[p][u];
else p=son[p][u];
}
cnt[p]=x;
}
pair<int,int> query(int x){
int res=0,p=0,a=s[x];
for (int i = 20; i >= 0; i -- ){
int u=a>>i&1;
if(son[p][!u]) res=res*2+1,p=son[p][!u];
else res=res*2,p=son[p][u];
}
pair<int,int> t;
t.first=res,t.second=cnt[p];
return t;
}
int main()
{
scanf("%d", &n);
s[0]=0;
for (int i = 1; i <= n; i ++ ){
scanf("%d", &a[i]);
s[i]=s[i-1]^a[i];
}
insert(0);
int res=-1;
for (int i = 1; i <= n; i ++ ){
pair<int,int> t=query(i);
if(t.first>res){
res=t.first;
ll=t.second+1;
rr=i;
}
insert(i);
}
printf("%d %d %d",res,ll,rr);
return 0;
}