求区间和用前缀和表示。
要使A和B的异或和最大,根据异或特征,就要让A和B的二进制序列“在高位尽可能不一样”(让异或结果的高位尽可能为1)。
所以考虑从高位到低位向trie插入二进制序列。由于只有0/1,此时trie就是一棵二叉树。
查找与某数x的最大异或时,要尽量“反着走”(不同异或才是1),即x某一位为0,在trie中就走1;为1则反之。
这样,由于从高到低插入trie,就会尽量在高位走向反向,获取最大异或。
另外,由于计算前缀和$s[i]-s[j]$,需要满足$i\ge j$,所以不能将前缀和$s$全部插入再计算。
插入$s[i-1]$后就计算与$s[i]$的最大异或,可以保证正确。
C++ 代码
#include <iostream>
using namespace std;
const int N=1<<22;
int n;
int son[N][2], cnt[N], idx;
int s[N],num[N];
void insert(int num,int id){ //插入前缀和s[i]的二进制序列和其下标i
int p=0;
for(int i=20;i>=0;i--){
int u=num >> i & 1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]=id;
}
int query(int num){ //查找当前trie中和序列num最大异或的s[i],返回其下标i
int p=0;
for(int i=20;i>=0;i--){
int u=num >> i & 1;
if(son[p][!u]) p=son[p][!u]; //能反着走就反着走,获取最大异或
else p=son[p][u];
}
return cnt[p];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++){
cin >> num[i];
s[i]=s[i-1]^num[i];
}
int l,r,ans=-1;
for(int i=1;i<=n;i++){
insert(s[i-1],i-1);
int id=query(s[i]); //只能在s[0]~s[i-1]中选择,立即查找
if((s[i]^s[id])>ans){
ans=s[i]^s[id];
l=id+1;r=i;
}
}
cout << ans << ' ' << l << ' ' << r;
return 0;
}