关于异或运算和代数和运算有很不错的性质:
\(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;
}