Codeforces #682 Div2 E. Yurii Can Do Everything

本番わりとすんなり通してるな。
https://codeforces.com/contest/1438/problem/E

問題

整数列Aが与えられる。
このうち、以下を満たす連続部分列A[L...R]は何通りか。

• 長さが3以上
• 先頭と末尾の値のxorが、中央の残りの要素の総和に等しい

解法

左端Lを固定したとき、右端の候補を列挙していく。
初手を長さ３(R=L+2)から初めて、Rを伸ばしていく。

A[L]-A[R]≦A[L] xor A[R]≦A[L]+A[R]であることを利用する。
今A[L] xor A[R] = sum(A[(L+1)...(R-1)])であるとする。
次のR'は、sum(A[(L+1)...(R'-1)])がsum(A[(L+1)...(R-1)])+sum(A[(L+1)...(R)])-A[L]あたりのところに来るので、二分探索でR'を求めて行こう。

int N;
int A[202020];
ll S[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i]=A[i];
		if(i) S[i]+=S[i-1];
	}
	
	ll ret=0;
	FOR(i,N) {
		int R=i+2;
		if(R>=N) break;
		if((A[i]^A[R])==A[i+1]) ret++;
		while(R<N) {
			ll s=S[R]-S[i];
			if(s<=A[i]) {
				R++;
			}
			else {
				R=lower_bound(S+R+1,S+N,S[R]+s-A[i])-S;
			}
			if(R>=N) break;
			if((A[i]^A[R])==S[R-1]-S[i]) ret++;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

なんか今Codeforcesが重くて、問題を確認するのに手間取った。