問題
解法
全探索すると $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; }