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行)