Xorto

题意:异或,选取任意不重叠的两个区间,使异或结果为0

如上述例子,我们可以选取 和 就是满足题意的
题解:相同元素异或为0,所以我们找到两个点 ,求与相同答案的个数.(额,这是句废话...)
先求解异或前缀和,然后枚举每个位置,统计该位置之前的所有前缀和,即把该位置当作右端点,然后枚举计算右端点之前的所有位,为左端点进行计数,同时当把该位当作右端点计算完之后,并用map存储,把该店当作左端点,逐个枚举右端点,用map查询相同的值,进行计数.

比如,当 运算到第一个8的时候,前面有1,2,3的异或值为0,且已经记录,然后当第一个8为右端点运算结束之后,变为左端点是,第一个8和第二个8异或结果为0,并且此时还有前面1,2,3异或为0,累计数+1
时间复杂度:

#include<cstdio>
#include<cstring>
typedef long long ll;

int a[10004],b[3000006];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(b,0,sizeof(b));
        a[0]=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            a[i]=a[i-1]^x;
        }

        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>0;j--)
                b[a[i]^a[j-1]]++;
            for(int j=i;j<n;j++)
                sum+=b[a[i]^a[j+1]];
        }

        printf("%lld\n",sum);
    }
    return 0;
}