ABC134 D - Preparing Boxes

f:id:tkr987:20200805235032p:plain

https://atcoder.jp/contests/abc134/submissions/15708918

1, 2, 3, ... の倍数毎に調べる要素数は調和級数になっている
後ろから情報を確定していく

f:id:tkr987:20200805235417p:plain

i+1以降の箱のうち倍数iの箱だけ考える。（i+1以降の）倍数iの箱に入っているボールの合計をsとしたとき、s % 2 = 0 ⇔ (s+1) % 2 = 1、s % 2 = 1 ⇔ (s+1) % 2 = 0、になる。つまり、i番目の箱にボールを入れると合計sの剰余が逆転する。1, 2, 3, ...の倍数の箱を調べる回数は調和級数になるので $O(N \log N)$ で済む。i番目の箱を確定させるためにはi+1以降の箱情報が必要なので、合計sの剰余と $a_{i}$ が異なればボールを入れて、同じならボールを入れない、という処理を後ろから繰り返せば答えが得られる。