D - Xor Sum 2 AtCoder Beginner Contest 098

問題概略

長さNの数列がある。あるl,rでAl ~ Arのxorと合計が等しくなるようなl,rの組み合わせを数えよう

制約

• $1\le N\le 2\times {10}^5$
• $0\le A_i<2^{20}$
• 入力はすべて整数である

解法

しゃくとり。

前回の長さの分を引き、新しい分を足す。という感じ

public static void main(String[] args)
{
    //longを忘れるなオーバーフローするぞ
    N = sc.nextInt();
    A = sc.nextLongArray(N);
    long res = 0;
    long sum = 0;
    for (int l = 0, r = 0; r < N && l < N; r++)
    {
        while (sum + A[r] != (sum ^ A[r]))
        {
            sum -= A[l];
            l++;
        }
        sum += A[r];
        long len = r - l + 1;
        res -= (len - 1) * (len) / 2;
        res += (len) * (len + 1) / 2;
    }
    System.out.println(res);
}