Xor Sum 2 / AtCoder - 4142

Input

Input is given from Standard Input in the following format:
N
A1 A2 … An

Output

Print the number of the pairs of integers  l and r(1 <= l <= r <= N)that satisfy the condition.

Sample Input 1

 4
 2 5 4 6

Sample Output 1

 5
(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition. (l,r)=(1,2) also satisfies the condition, since A1 xor A2=A1 + A2=7. There are no other pairs that satisfy the condition, so the answer is 5.

Sample Input 2

 9
 0 0 0 0 0 0 0 0 0

Sample Output 2

 45

Sample Input 3

 19
 885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

Sample Output 3

 37

题意

n个数，有多少个区间的XOR等于区间的和

题解

枚举左端点，滑动右端点（双指针），找答案

代码

#include<cstdio>
using namespace std;
const int N = 2 * 1e5 + 10;

int n, a[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    int j = 1;//右端点
    long long suma = 0, sumb = 0, ret = 0;//suma: XOR  sumb: 和
    for(int i = 1; i <= n; i++){//枚举左端点
        while(j-1 <= n && suma == sumb){//滑动右端点
            suma ^= a[j], sumb += a[j];//一波操作666？？
            j++;//右端点往右移
        }
        ret += j - i - 1;
        //跳出循环是因为j位置的2个数不符合条件，所以将这2个位置从suma和sumb中剔除
        suma ^= a[j-1], sumb -= a[j-1];
        //左端点会往右移，所以将最左边的2个位置从suma和sumb中剔除
        suma ^= a[i], sumb -= a[i];
        //跳出循环是因为j位置的2个数不符合条件，所以j-1是满足条件的最右位置
        j--;
    }
    printf("%lld\n", ret);
    return 0;
}

PS

一定要用long long，不然会WA掉！
这是为什么呢？其实很简单我们来做个简单的计算
int 最大值为 2147483647 
long long 最大值为 9223372036854775807 
本题最多200000个数，每个数最大2^20(1048576)
所以ret最大为 200000 * 1048576 = 209715200000
一比较用int肯定超了，所以用long long

Xor Sum 2 / AtCoder - 4142

原文：https://www.cnblogs.com/Little-Turtle--QJY/p/12384557.html