ABC 155 F Perils in Parallel 解説
まず思うこと
ソートしても題意が変わらないので，ソートします．(頻出中の頻出なので普通やる．)
ついでに座標圧縮もしちゃいましょう．
これで，問題が次のように変わりました．
爆弾が N 個あり，i 番目の爆弾は座標 i にある．各爆弾のオンオフ状態は s[i] である．
コードが M 本あり，j 番目のコードを切ると爆弾 l[j] 以上 r[j] 未満が切り替わる．(ついでに半開区間に変えた．)
ちなみに，この問題の場合，座標圧縮はしなくても解ける気がしますが，思考しやすくなるので題意が変わらないのなら圧縮すればよいです．
ゴールを見据える
便宜上，配列 s の前後に番兵を置いて，書き並べてみます．例えば
01101001100
こんな感じ．この隙間に注目します．
01101001100
^^^^^^^^^^^^
例えば，最初の部分，
01
これらは値が一致していませんが，最終的には 00 と値を一致させたいわけです．
よって，どちらかだけのオンオフを切り替える必要があります．
つまり，l[j] または r[j] がこの隙間を指し示すコードを奇数本切る必要があります．
逆に，隣接する値が一致している隙間では，コードを切る必要はありませんが，偶数本のコードを切ってもよいです．
グラフとみる
ここですこしひらめきが必要ですが，この隙間をノード，コードを辺とみて，その部分グラフを取ることにします．
部分グラフに選ばれた辺と切るコードが対応しています．
このとき，左右が一致していない隙間では，そのノードから出る辺を奇数本選択する必要があり，
左右が一致している隙間では，そのノードから出る辺を偶数本選択する必要があります．
DFS
辺を奇数本選ばなければならない頂点①から，DFS をして，他の辺を奇数本選ばなければいけない頂点②にたどり着きます．そのパスのコードをすべて切ることにします．
①―〇―〇―〇―〇―②
例えばこんな感じのパスの辺を部分グラフに選んだ (対応するコードを切った) として，ちゃんと①②から出ている辺は奇数本，〇から出ている辺は偶数本になっています．
なお，コードはつなぐことができると考えても問題ありません．
時間計算量がやばい
上の解法だと，O(N(N+M)) かかってしまい，困ります．
要は s[i] = 1 になっている辺同士のパスを見つければ (作れば) いいわけです．
適当な部分木を取って根つき木にします．
辺が奇数本でないといけない各頂点について，深い方から少しずつ上っていきます．別の上ってきた誰かと鉢合わせたら無事ペア成立，パス完成です．
