ARC098 D : Xor Sum 2(500)

作成日:2018.09.29
最終更新日:2018.09.29

問題概要

問題本文

 長さ$N$の整数列$\{A_i\}$において、$A_l \; xor \; A_{l+1}\;$$xor \; ... \;$$xor \; A_r$$= A_l$$+ a_{l+1}$$+ ...$$+ A_r$を満たす整数$l,r$($1 \leq l$$\leq r$$\leq N$)の組の個数を求めよ。
制約
$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i \lt 2^{20}$

考え方

 $xor$をとるので二進数表記した時の桁ごとに考える。 $A_i \; xor \; A_j = A_i + A_j$となる条件を調べるために、まずは繰り上がりのない最下位bitを考える。 すると$A_i$,$A_j$の最下位bitがともに$1$でなければ良いことが分かる。 これは最下位bitにおいて繰り上がりが生じないということである。 つまり下位bitから順番に考えていけば、どの桁においてもともに$1$にならないことが条件であると分かる。
 以上より$A_l,A_{l+1},...,A_r$で下から$k$bit目が$1$となっているものは高々$1$個であるような$l,r$の組の数を求めれば良い。 $l$を固定した時、$r = r'$でこの条件を満たさなければ、$r \gt r'$においても条件を満たさない。 逆に$r = r'$でこの条件を満たせば、$l \leq r \lt r'$においても条件を満たす。 よって各$l$において$r = r_l - 1$の時は条件を満たすが、$r = r_l$の時は条件を満たさないような$r_l$が求まれば、答えは$\sum (r_l - l)$となる。 さらに同様に考えると$l \lt l'$ならば$r_l \leq r_{l'}$であることが分かるから、尺取り法によりすべての$l$において$r_l$を求めることができそうである。 これは今見ている区間に含まれる要素すべての$xor$を高速に更新できれば良いが、増減する要素との$xor$をとれば可能である。 また1つ要素を増やした時に条件を満たすかは、区間の要素すべての$xor$と新たに増やす要素のbitごとの$and$が$0$であるかを調べれば良い。 以上より、この尺取り法は$O(N)$で動作するから十分高速である。

ソースコード

マクロ等はこちら

int N;
int A[200010];

int main(){
	cin >> N;
	repp(i,0,N) cin >> A[i];
	int r = 0 , x = 0;
	LL ans = 0;
	repp(l,0,N){
		while(r < N && !(x&A[r])) x ^= A[r++];
		ans += r - l;
		x ^= A[l];
	}
	cout << ans << endl;
	return 0;
}

解法まとめ

 尺取り法を用いる。 区間に含まれる要素すべての$xor$と新たに加える要素のbitごとの$and$が$0$である限り区間を伸ばしていき、各$l$において伸ばせなくなった時の区間の幅の総和が答えとなる。(7-14行)

ARC098の他の問題 C E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告