[ARC098B] Xor Sum 2

关于异或运算和代数和运算有很不错的性质:

\(xor_{i = 1} ^ {n}a_i \leq \sum_{i = 1} ^ n a_i\)

所以我们考虑一段区间按题目来说是合法的,即 \(xor_{i = 1} ^ {n}a_i = \sum_{i = 1} ^ n a_i\) 是满足一段不符合,则整段不符合的性质的。
那么可以用 \(two-point\) 。

[ARC098B] Xor Sum 2
#include<iostream>
#include<cstdio>
#define ll long long 
#define N 200005

ll n;
ll a[N];
ll sum[N],xsum[N];//sum >= xsum

int main(){
	scanf("%lld",&n);
	for(int i = 1;i <= n;++i){
		scanf("%lld",&a[i]);
		sum[i] = sum[i - 1] + a[i];
		xsum[i] = xsum[i - 1] ^ a[i];
	}
	ll l = 0;
	ll ans = 0;
	for(int r = 1;r <= n;++r){
		while(l < r && (sum[r] - sum[l] != (xsum[r] ^ xsum[l])))
		l ++ ;
		ans += r - l;
	}
	std::cout<<ans<<std::endl;
}

上一篇:从PHP开始学*** -- 数据类型及判断语句


下一篇:第101章 Caché 函数大全 $ZCYC 函数