ABC155 F. Perils in Parallel
問題
数直線上にN個の爆弾が仕掛けられており、i番目の爆弾はA_iの位置で、スイッチの状態がB_i(OFFは0、ONは1)で与えられる。
制御装置にはM本のコードがあり、j番目のコードを切ると、L_j以上R_j以下の位置にある爆弾のスイッチの状態が入れ替わる。
切るコードをうまく選んで、すべての爆弾の状態をOFFの状態にできるか？
できる場合、どのコードを使うと良いか、答えよ。
制約
- 1 <= N <= 10^5
- 1 <= A_i <= 10^9, A_iは互いに相異なる
- 1 <= M <= 2*10^5
- 1 <= L_j <= R_j <= 10^9
解法
解説放送より。
範囲に対して操作するのは大変なので、imos法のように、値の差分を保持するような数列を考える。これによって、範囲は始点と終点の2箇所で扱うことができる。
例えば、数直線上の爆弾を左からスイッチの状態が001101のような場合、
0 0 0 1 1 0 1 0 # 元の状態の両端に0を加えたもの 0 0 1 0 1 0 1 # 上の各隣り合う要素間の差分(xor)を取ったもの
(下から上の数列に戻すには累積xorを前からとっていけば良い)
差分列の方で、要素を2つ選んでそれぞれ0/1を反転させれば範囲更新に対応する処理が行える。
次に、各コードについて考える。
各コードは、差分列でのどの位置とどの位置の0/1を反転させるかに対応している。
この位置は、適当に二分探索などで計算しておくことができる。
したがって、問題は、コード(2要素を選んで0/1を反転)をうまく選んで、差分列のすべて要素を0にできるか？を解くことになる。
差分列のある1になっているような要素に注目すると、そこからコードでつながる他の要素の状況に合わせて1を0にしなければならない。
なので、ある1になっている要素について、そこからコードでつながる連結成分を考える。
(この連結成分は多重辺やループなどを含んでいる)
辺(コード)を選ぶと両端の要素を反転させることができるが、どのように選べばすべての要素を0にすることができるか？
これは、DFS木を作って、リーフから決めていけば求められる。
もし、ある要素eにおいて、子の要素cが1だった場合、eとcの間の辺は使う必要がある。
要素e自体の値は、子の要素に対し、使った辺の数と、要素eの元の0/1によって決まる。これをルートまで繰り返して、ルートでの値が0になればよい。
もし、ルートでの値が1だった場合は、不可能。
