AT4142

Aryper · 2021-09-04 21:00:42 · 个人记录

[ARC098B] Xor Sum 2

被迫害到了这种程度。。

然后是一个考察对 \operatorname{xor} 的理解的题目。

异或和与和相等的一个很重要的条件是不进位。简单来说，如果在加法中产生了进位，异或和就绝对不可能与和的数值相等。再换句话说，不同数字异或和上的每一位，有且仅能有 1 个 1 存在，不然必然会在加法中产生进位。

那么再换句话说，如果异或和目前已经与和不相等了，就说明加法中已经产生了进位，那么这个异或和与和就永远不可能相等了。从严谨一些的角度理解，设异或和为 x，前缀和为 c，我们必然会有 x\le c，如果说 x<c 了，那不管后面再异或什么，最终一定不可能再使 x=c 了。

所以说可以直接用一个双指针操作。

时间复杂度 O(n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,ans;

ll a[N+5],c[N+5],c_[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    for(ll i=1,j=1;i<=n&&j<=n;i++) {
        a[i]=read();
        c[i]=c[i-1]^a[i];
        c_[i]=c_[i-1]+a[i];
        while((c[j-1]^c[i])!=c_[i]-c_[j-1]) j++;
        ans+=i-j+1;
    }

    write(ans);

    return 0;
}