AT_arc098_b [ABC098D] Xor Sum 2 题解

思路

对非负整数做加法时，只要某一二进制位出现进位，区间和就会大于区间异或。因此区间和等于区间异或，当且仅当区间内任意两个数在二进制上没有公共的 $1$ 位。

这个条件对区间具有单调性：合法区间的任意子区间仍合法，而向区间加入新元素后若产生公共位，只能通过删除左端元素恢复合法性。

做法

用双指针维护当前右端点之前的最长合法窗口 $[l,r-1]$，并用 mask 保存窗口内所有数的异或。因为窗口合法，各元素的 $1$ 位互不重叠，所以这里的异或也等于按位或。

加入 $A_r$ 前，只要 mask 与 $A_r$ 存在公共 $1$ 位，就不断从左端删除元素；删除可用异或完成。随后加入 $A_r$。此时所有以 $r$ 为右端点、左端点位于 $[l,r]$ 的区间都合法，共有 $r-l+1$ 个，将其加入答案。

正确性证明

维护窗口中的任意二进制位至多由一个元素贡献，因此窗口内加法没有进位，窗口和等于窗口异或。

处理 $A_r$ 时，若它与窗口存在公共位，则包含产生冲突的最左元素及 $A_r$ 的区间不合法；不断移动左端点，直到所有公共位消失，得到以 $r$ 结尾的最长合法区间 $[l,r]$。根据子区间封闭性，左端点为 $l,l+1,\ldots,r$ 的区间全部合法，而任何更小左端点对应的区间都包含尚未排除的冲突，均不合法。因此本轮恰好计数所有以 $r$ 结尾的合法区间。

对每个右端点重复上述过程，每个合法区间被计数一次且仅一次，所以最终答案正确。

复杂度

每个元素至多进入和离开窗口一次，时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。

参考实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> values(n);
    for (int &value : values) {
        cin >> value;
    }

    long long answer = 0;
    int left = 0;
    int mask = 0;
    for (int right = 0; right < n; ++right) {
        while ((mask & values[right]) != 0) {
            mask ^= values[left];
            ++left;
        }
        mask ^= values[right];
        answer += right - left + 1;
    }
    cout << answer << '\n';
    return 0;
}