ABC155F Perils in Parallel
問題文
AlDebaran 王国の侵攻によって、AtCoder 王国の各地に爆弾が仕掛けられてしまいました。
幸いにも AtCoder 王国 ABC 隊の健闘により制御装置の一部が手に入ったので、あなたはこれを使って解除を試みることにしました。
仕掛けられた爆弾は N 個あり、1 から N の番号がついています。爆弾 i は座標 Ai にあり、電源は Bi=1 のときオンに、Bi=0 のときオフになっています。
制御装置には M 本のコードがあり、1 から M の番号がついています。コード j を切ると、座標が Lj 以上 Rj 以下の全ての爆弾の電源のオン・オフが切り替わります。
切るコードをうまく選ぶことで全ての爆弾の電源をオフにできるか判定し、できるならばそのようなコードの組合せを 1 つ出力してください。
制約
- 入力はすべて整数
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109 (1 ≤ i ≤ N)
- Ai は互いに相異なる
- Bi は 0 か 1 のいずれか (1 ≤ i ≤ N)
- 1 ≤ M ≤ 2 × 105
- 1 ≤ Lj ≤ Rj ≤ 109 (1 ≤ j ≤ M)
競プロ道場鯖の set e の 2-6 。
「[l, r]を反転」は、
「[0, l-1]及び[0, r]を反転」
と言い換えられる。また、隣接する要素同士のxorを取った数列 {Ci} (C1 = B1, C2 = B1 xor B2, C3 = B2 xor B3, ... , Cn = Bn-1 xor Bn, Cn+1 = Bn)を考えると、
「ClとCr+1を反転」
と言い換えられる。
また、グラフを考え、Ciをグラフの頂点 i に対応させると、
「頂点lと頂点r+1の間に辺を張る」
と言い換えることもできる。ただし、Ciは頂点iの次数だけ反転されるものと考える。
ここで、{Ci}は要素がn+1個になっており、余分な自由度が1増えているように見えるが、この数列の要素の全てのxorを取ると0になる、という隠れた制約があるので自由度は変わっていない。（各Biが2回登場するため）
{Bn} = (0,0,...,0) ⇔ {Cn} = (0,0,...,0) なので、頂点iの次数の偶奇が{Cn}の初期値と一致するように辺を張ればよい。これは各連結成分について適当な全域木を取って葉から考えればよい。
全域木を考えればよい理由だが、「全域木に含まれる辺だけでは条件を満たす解が構築できない⇒元のグラフでも条件を満たす解が構築できない」が示せればよい。
全域木で条件を満たす解が構築できないのは、葉から順に考えて最後に残った頂点が条件を満たさない場合である。ある辺について、その辺を使うにしても使わないにしても全頂点の次数の和の偶奇は変わらない。考察を進めると、連結成分に含まれる頂点のうち、次数が奇数となるべきものの数が奇数となることが条件を満たす解が構築できない必要十分条件であることが分かる。逆に解が構築できるなら、全域木で考えて葉から考えていって残った最後の頂点は条件を満たしていることが分かるだろう。よって、全域木で考えればよい。
葉から順に考える方法として、オイラーツアー風にDFSをする方法と、辺を削除（実際には各頂点の次数を記憶しておいて、それを減らしていけばよい）していく方法がある。どちらでも計算量は変わらず実行時間もほぼ同じだ。
以下の実装ではオイラーツアーを採用している。
