ABC155 F - Perils in Parallel - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

爆弾が ${N}$ 個あり， ${i}$ 番目の爆弾は座標 ${A_i}$ にあって ${B_i=0}$ のときオフ， ${B_i=1}$ のときオンになっている． ${M}$ 本のコードがあり， ${j}$ 番目のコードを切ると，座標が ${L_j}$ 以上 ${R_j}$ 以下のすべての爆弾の電源のオン・オフが切り替わる．切るコードをうまく選ぶことですべての爆弾の電源をオフにすることができるか判定し，できるならばそのコードの組合せを一つ出力せよ．

${2\leq N \leq 10^5\\ 1\leq A_i\leq 10^9\\ B_i\in \{0,1\}\\ 1\leq M\leq 2×10^5\\ 1\leq L_j\leq R_j\leq 10^9}$

解説

公式解説が急にグラフを作り出してるので，自然な流れ重視で説明します．公式解説の前半に書かれてる処理はすでに行っているものとします．

隣り合う爆弾の状態のXOR(状態が違うなら ${1}$ ，同じなら ${0}$ )を考える． ${[l,r]}$ 番目の爆弾を切り替えるとき， ${l-1}$ 番目と ${l}$ 番目の爆弾の状態のXOR(これを ${X_{l-1}}$ とします)， ${r}$ 番目と ${r+1}$ 番目の爆弾の状態のXOR( ${X_{r}}$ )のみが切り替わります．便宜上 ${0}$ 番目と ${N+1}$ 番目の状態 ${0}$ の爆弾があるとします．このように考えることで，区間を変更し ${0}$ にする問題が2点( ${X_{l-1},X_r}$ )を変更し ${X_0}$ から ${X_N}$ を ${0}$ にする問題になりました．

入力例 ${1}$ での例

f:id:kanpurin:20210503224214p:plain:w400

ここで上図を見ると， ${X_2}$ を変更できるのは緑のコードだけです． ${X_2=1}$ であることから緑のコードは必ず使うことになります．緑のコードを使うと次は ${X_1}$ を変更できるのが青のコードだけになります．このとき ${X_1=0}$ なので青のコードは使いません．このようにして変更できるコードが ${1}$ つだけの ${X_i}$ がある限り決めていけばいいです．