【牛客每日一题】 4.13 Xorto（前缀异或和，枚举优化/映射）

链接：https://ac.nowcoder.com/acm/problem/14247
来源：牛客网
题目描述

给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

输入描述:
第一行一个数n表示数组长度；第二行n个整数表示数组；

输出描述:
一行一个整数表示答案。
示例
输入

3
0 0 0

输出

5

说明

思路
这道题要求区间异或和，优化可以用前缀异或和：设表示 的区间异或和，那么的区间异或值就等于，不理解的可以点开学习一下
本题中n<=10000，所以 就够了可以水过 ，直接计算前缀异或和，然后枚举优化即可。这里用到一个映射的思想，枚举i，用j 在i的左半边求区间异或和相同的个数存在vis数组里（类似map映射），然后枚举右半边相同的ans加上即可（异或相同为0嘛）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=750007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

ll n,m,a[N],ans;
ll pre[N],vis[N];
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
    scanf("%lld",&a[i]),pre[i]=pre[i-1]^a[i];
    over(i,1,n)
    {
        over(j,1,i)
            vis[pre[i]^pre[j-1]]++;
        over(j,i+1,n)
            ans+=vis[pre[j]^pre[i]];
    }
    printf("%lld\n",ans);
    return 0;
}

附官方题解：

顺便说一下牛客新推出的这个每日一题版块真的挺不错的，讲解也很详细，而且现在写博客还送牛币，非酋再也不用担心自己没办法白嫖牛客礼物啦，非常适合我这种蒟蒻学习算法：https://ac.nowcoder.com/discuss/390407?type=101&order=0&pos=2&page=1