奶牛异或

奶牛异或

分析

1. 先假设s [ i ] = a [ 1 ] ^ a [ 2 ] ^ ... ^ a [ i ]，那么
   

2. 在每次将 a [ i ] 加入树的时候，记录它的尾节点对应的是哪一个下标

代码

/*
(写点什么吧...)
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e5+10;

int n,tot,sum;
int a[N],tr[2][N*20],be[20*N];

inline void insert(int x,int id)
{
    int rt=0;
    for (int i=20;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(!tr[c][rt]) tr[c][rt]=++tot;
        rt=tr[c][rt];
    }

    be[rt]=id;//记录rt节点对应的下标
}

inline int find(int x)
{
    int ret=0,rt=0;
    for (int i=20;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(tr[c^1][rt])
            ret+=(1<<i),rt=tr[c^1][rt];
        else rt=tr[c][rt];
    }

    sum=ret;
    return be[rt];
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=2;i<=n;i++) a[i]^=a[i-1];
//先处理异或前缀和
    insert(0,0);//因为可能选到s[1~i]
    int ans=-1,x=0,y=1;
    for (int i=1;i<=n;i++)
    {
        int now=find(a[i]);//找到使结果最小的值的下标
        if(sum>ans) ans=sum,y=i,x=now;//判断大小
//        else if(ans==sum&&(i-now<y-x)) y=i,x=now;
//否则选择一个最短的区间
        insert(a[i],i);
    }

    printf("%d %d %d\n",ans,x+1,y);

    return 0;
}