Author: loop3r
Date: 20260322
tag: 双指针
link: https://atcoder.jp/contests/abc098/tasks/arc098_b

问题描述

有一个长度为 $N$ 的整数序列 $A$。

请你求出满足以下条件的整数对 $(l,r)$ 的个数（$1\le l\le r\le N$）：

• $A_l\mathrm{xor}{A}_{l+1}\mathrm{xor}\cdots \mathrm{xor}{A}_r=A_l+A_{l+1}+\cdots +A_r$

输入格式

输入以如下格式从标准输入读入：

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出满足条件的整数对 $(l,r)$ 的个数。

分析

异或（相同为 $0$，不同为 $1$）和是不进位的加法，有 $a\oplus b\le a+b$。

设 $i$ 指针初始指向首位置，$j$ 指针初始指向首位置的前一位置。

设 $s_1$ 为算术和，$s_2$ 为异或和。

每次循环内，如果 $s_1+a[j+1]==(s_2\oplus a[j+1])$，则不停的移动 $j$ 指针，即 s1 += a[j + 1]; s2 ^= a[j + 1]; j++;。当循环结束时 $j$ 指针指向合法区间的右端点。

更新答案：ans += j - i + 1;。

移动 $i$ 指针：s1 -= a[i]; s2 ^= a[i]; i++;。

参考代码

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

int n, a[200010];
long long s1, s2, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int i = 1, j = 0;
    while (i <= n) {
        while (j + 1 <= n && s1 + a[j + 1] == (s2 ^ a[j + 1])) {
            s1 += a[j + 1];
            s2 ^= a[j + 1];
            j++;
        }

        ans += j - i + 1;
        s1 -= a[i];
        s2 ^= a[i];
        i++;
    }
    cout << ans << endl;

    return 0;
}