知识点
前缀和,01trie树(01Trie树不懂的可以去 牛客看看专题, 基本模板,可以结合理解一下Trie树
简单解释一下trie数组的含义,trie[i][j]这个值是指与第i个节点的j边(0或1)相连的下一个节点的角标。每次要创建新的节点只用将上一个节点指向下一个节点即可。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e7+10;
int sum[maxn] , trie[maxn][2] , ID[maxn] , mark = 1;
void insert(int m, int w , int num , int id){
if (w<0){
ID[m] = id;
return ;
}
int tmp = (num>>w)&1;
if (!trie[m][tmp])trie[m][tmp] = ++mark;
insert(trie[m][tmp],w-1,num,id);
}
int ask (int m , int w , int num){
if (w<0)return ID[m];
int tmp = (num>>w)&1;
if (trie[m][!tmp])return ask(trie[m][!tmp],w-1,num);
return ask(trie[m][tmp],w-1,num);
}
int main(){
int n , tmp , res = 0 , start = mark , left = 1 , right = 1;
scanf("%d",&n);
for (int i = 1 ; i <= n ; i ++ ){
scanf("%d",&tmp);
sum[i] = (sum[i-1]^tmp);
}
for (int i = 1 ; i <= n ; i++){
insert(start,22,sum[i-1],i);
int x = ask(start,22,sum[i])-1;
if (res < (sum[x] ^ sum[i])){
res = (sum[x]^sum[i]);
left = x+1;
right = i;
}
}
printf("%d %d %d\n",res,left,right);
}
`