原题链接：AtCoder Regular Contest 098 D

题意

题意非常简单，给一个含n个整数的序列 $A_1$, $A_2$, $A_3$…
求存在多少对$(l, r)且l <= r $ 使得 $A_l$ + $A_{l+1}$ + … + $A_{r}$ = $A_l$ xor $A_{l+1}$ xor … xor $A_{r}$ 成立。
输入：
第一行n，代表有n个数。第二行n个数用空格隔开代表序列。

样例

样例输入：

4
2 5 4 6

样例输出：

5

分析

这一段是废话，可以直接往下拉。

一开始看到这个题，我的想法是分别求序列的前缀和和前缀异或，分别记做$presum[N]$ 和$ prexor[N]$好了。然后原来的式子就变成了$presum[r] - presum[l-1] == prexor[r] xor prexor[l-1]$。然后再通过一些数学技（luan）巧（gao）变换成一个$f(presum[l-1], prexor[l-1]) = f(presum[r],prexor[r])$的形式，然后对两个序列操作一下，最后计数求值就可以了。

然鹅数学菜鸡的我想了一个小时都没想到怎么变换。就去看题解，发现是双指针。

首先我们需要知道xor的一个性质：
$$ a + b = a xor b + ((a & b) << 1) $$
然后注意到如果要两数之和等于两个数异或的话，那么这两个数按位与必须为0。
所以此时有一个很重要的性质出现了，如果区间$(l, r)$满足题目的等式的话，区间内任意一个连续子区间都满足这个性质。所以问题转化成了，对于每一个左端点，寻找最远的右端点，使之满足这个性质。就可以自然地（并不）联想到双指针。

菜鸡代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
ll arr[N];
ll n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> arr[i];//存数组
    }
    ll ans = 0; //记录答案
    ll right = 0; //右指针
    ll curr = 0;//用来维护区段异或，其中异或的零元是0
    for(int left = 0; left < n; left ++) {
        //固定左指针的位置
        while(right < n && (arr[right] & curr) == 0) {
            //尝试寻找满足条件的最远的右指针
            curr ^= arr[right];
            right ++;
        }
        ans += (right - left);//这里是增加每一个元素作为最左端的元素对数量
        curr ^= arr[left];//左指针右移动
    }
    cout << ans << endl;
    return 0;
}

菜鸡感想

这题是个双指针思想的好题，需要对双指针的应用原理有很好的认知。其次一个比较重要的是事情是如何从思维误区中跳出来。一开始的那个想法其实是适用于很多长得差不多的题目的，但是不适用于这道题。所以怎么跳出思维误区也是一个需要训练的点。