[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;
}

[ARC098B] Xor Sum 2

上一篇:Hadoop 运行模式之本地&伪分布式模式


下一篇:131. 分割回文串