自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:49:17，当前版本为作者最后更新于2023-08-13 18:32:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

考虑两个零异区间：

• 如果它们包含或不交，那么翻转一个对另一个没有影响。

• 如果它们相交，设区间分别为 $[l1,r1],[l2,r2]$，有 $l1\leq l2\leq r1\leq r2$。

  根据异或性质，有 $[l1,l2-1]=[l2,r1]=[r1+1,r2]$，其中等号表示异或和相等。

  可以发现，如果翻转了一个零异区间，另一个区间仍然存在，只是其左端点会移动。

所以，翻转区间不改变零异区间个数。直接用前缀异或和统计一下即可。

code

#include<stdio.h>
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,a[100009],cnt[1<<20];long long ans;
main()
{
	read(n);cnt[0]=1;
	for(int i=1;i<=n;++i)
	{
		read(a[i]);a[i]^=a[i-1];
		ans+=cnt[a[i]]++;
	}
	printf("%lld",ans);
}