奶牛异或

题意：
给你一个长度为n的序列，让你选择你个连续的子序列做Xor操作求最大值为多少？并且该区间是什么？（如果有多个解，则取右边界最小（第一关键词），区间长度最短（第二关键词））。

思路：
对数组求前缀异或和，即求[1,2][1,3]....[1,n]等区间的异或和，然后你将二个区间异或后可以发现是一个连续区间的异或和。然后用01trie求取结果。

注意当n=1时的结果。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[33], cnt[3200005][2], ji=1;
ll pa[100005];
ll ma=-1;

void Insert()
{
    int now=0, i=31;
    while(i>=0)
    {
        if(cnt[now][a[i]]==-1)
        {
            cnt[now][a[i]]=ji;
            ji++;
        }
        now=cnt[now][a[i]];
        i--;
    }
}

ll fun()
{
    ll now=0, p=0, k=(1LL<<31), i=31;
    while(i>=0)
    {
        if(a[i]==1&&cnt[now][0]!=-1)
        {
            p=p+k;
            now=cnt[now][0];
        }
        else if(a[i]==0&&cnt[now][1]!=-1)
        {
            p=p+k;
            now=cnt[now][1];
        }
        else if(a[i]==1&&cnt[now][1]!=-1)
        {
            now=cnt[now][1];
        }
        else
        {
            now=cnt[now][0];
        }
        i--;
        k=k/2;
    }
    return p;
}

int main()
{
    int n, r=-1;
    scanf("%d",&n);
    memset(cnt,-1,sizeof(cnt));
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&pa[i]);
    }
    ma=pa[0];
    for(int i=0; i<n; i++)
    {
        if(i!=0)
        {
            pa[i]=pa[i-1]^pa[i];
        }
        int x=pa[i];
        for(int j=0; j<32; j++)
        {
            a[j]=x%2;
            x=x/2;
        }
        Insert();
        ll pan=fun();
        if(pan>ma)
        {
            ma=pan;
            r=i;
        }
    }
    //printf("%lld %lld\n",pa[1],pa[2]);
    ll l=-1;
    for(int i=r-1; i>=0; i--)
    {
        if((pa[i]^pa[r])==ma)
        {
            l=i;
            //printf("%lld %lld\n",pa[i],pa[r]);
            //printf("l=%lld\n",r);
            break;
        }
    }
    if(pa[0]==ma)
    {
        cout << pa[0] << " " << 1 << " " << 1 << endl;
    }
    else
    {
        cout << ma << " " << l+2 << " " << r+1 << endl;
    }
    return 0;
}