奶牛异或

题意

给你一个序列，让你找出一个连续子序列使得其异或和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。

思路

同一个值异或两遍就是，所以用前缀记录从到的异或和，到异或和就是。所以答案就转化成了，求和的异或和最大。

做法

用字典树来实现记录和查找就好了。记得以此按照题目要求比较。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e7+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n;
int ans=-1<<29,numi=0,numj=0,maxx=0;
int tree[N],f[N]; 

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void build(int x,int y,int z,int p)
{
    if (z==-1){tree[p]=y;return;} 
    int yh=z; 
    if((x&(1<<yh))!=0) build(x,y,yh-1,p+p+1);
    else build(x,y,yh-1,p+p); 
    if(tree[p+p]!=0||tree[p+p+1]!=0) tree[p]=1;
}


int search(int x,int y,int z,int p)
{ 
  if(z==-1)  return tree[p]; 
  int yh=z; 
  if(((x&(1<<yh))!=0&&tree[p+p]>0)||(tree[p+p+1]==0)) return search(x,y,yh-1,p+p);
  else if(((x&(1<<yh))==0&&tree[p+p]>0)||(tree[p+p]==0)) return search(x,y,yh-1,p+p+1); 
} 

int main()
{
    n=read();
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        int t=read();
        f[i]=f[i-1]^t;
        int a=0,j=f[i];
        while(j!=0)    j/=2,++a;
        maxx=max(maxx,a);
    }
    for(int i=1;i<=n;++i)
    { 
        int j=search(f[i],i,maxx-1,1)+1; 
            int zhi=f[i]^f[j-1]; 
        if((zhi>ans)||(zhi==ans&&i<numj)||(zhi==ans&&i==numj&&i-j+1<numj-numi+1))
          ans=zhi,numi=j,numj=i; 
        build(f[i],i,maxx-1,1); 
     } 
      printf("%d %d %d",ans,numi,numj); 
    return 0;
}