Solution

要求选出一段子序列使得异或值最大。发现异或运算具有类似于前缀和的性质：由于 的性质，可以快速消除前缀影响。

设 为 到 的异或值，则 即为 到 的异或值。问题转化为对每个 查询使得异或值最大的 ，字典树实现即可。

需要注意的是，异或运算的优先级低于 ，判断时需要加括号。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m,tot=1,pre[N],trie[N<<5][2];
void Insert(int x){
    int y,p=1;
    for(int i=21;i>=0;i--){
        y=(x>>i)&1;
        if(!trie[p][y])
            trie[p][y]=++tot;
        p=trie[p][y];
    }
}
int query(int x){
    int y,p=1,res=0;
    for(int i=21;i>=0;i--){
        y=((x>>i)&1)^1;
        if(trie[p][y])
            p=trie[p][y],res|=(1<<i);
        else if(trie[p][y^1])
            p=trie[p][y^1];
        else
            break;
    }
    return res;
}
int main(){
    cin>>n;
    int x;
    for(int i=1;i<=n;i++)
        cin>>x,pre[i]=pre[i-1]^x;
    int ans=-1,l,r;
    Insert(0);
    for(int i=1;i<=n;i++){
        x=query(pre[i]);
        if(x>ans)
            ans=x,r=i;
        Insert(pre[i]);
    }
    for(int i=r-1;i>=0;i--)
        if((pre[i]^pre[r])==ans){
            l=i+1;
            break;
        }
    cout<<ans<<" "<<l<<" "<<r;
    return 0;
}