atcoder ABC 098 D - Xor Sum 2

問題

D - Xor Sum 2

解法

全探索すると $O(N{^2})$となり間に合わないため、計算量を減らす工夫が必要になる。

この問題は単調増加する区間の数え上げなので、尺取り法の要領で解くことができる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0;i<n;i++)

int main() {
  int n,sum=0,r=0; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  ll ans=0;
  REP(l,n) {
    while(r < n) {
      // xor と sum が等しくなければ条件を満たさないので終了する
      if ((sum^a[r]) != (sum+a[r])) break;
      sum += a[r];
      r++;
    }
    ans += r-l;

    if (r == l) r++;
    sum -= a[l];
  }

  cout << ans << endl;
  return 0;
}