题解 AT4142 【[ARC098B] Xor Sum 2】

一道较简单的题目。

题意

给你一些数字，求有多少区间的异或和等于区间的数字之和。

题解

如果直接枚举的话，时间复杂度略高。怎么办呢？可以用两指针，一个指针固定，一个指针滑动。而后，就可以找到最大满足条件的端点了。

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N=200020;
long long s,n,a[N],ans=0;
int main()
{
	cin>>n;
	//memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++) cin>>a[i];
	long long j=0;
	long long suma=0,sumb=0;
	for(int i=1;i<=n;i++)
	{
		while(j+1<=n&&sumb+a[j+1]==(suma^a[j+1]))//指针滑动
		{
			suma^=a[j+1];
			sumb+=a[j+1];
			j++;
		}
		ans+=j-i+1;
		suma^=a[i];
		sumb-=a[i];
	}
	cout<<ans;
	return 0;
}