ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #673 (Div. 1) D. Graph and Queries

Problem - D - Codeforces

コンテスト中に自分が通した解法を書きます。

問題概要

 n 頂点 m 辺の無向グラフが与えられ、頂点  i には相異なる整数  p_{i} が書かれている。

以下のクエリを合計  q 個処理せよ。

  • 1 v:頂点  v と連結な頂点の中で最も大きい整数が書かれている頂点  u を探し、 p_{u} を出力する。その後、 u に書かれている整数を  0 に書き換える。
  • 2 i:辺  i を削除する。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le m \le 3\times 10^{5}
  •  1 \le q \le 5\times 10^{5}

解法

辺を削除するクエリなので、逆から見ていけばUnion-Findが使えます。一方クエリ1に答えるためには「それ以前のクエリでどの整数が既に取られているか」の情報が必要なので、前から処理していく必要があります。

よって、辺が削除される過程を逆からUnion-Findで処理し、そのロールバックを行うことで前からクエリを処理できるようにするという方法を取ることにします。

Union-Findのロールバックは、経路圧縮を捨てればシンプルです。findクエリでは内部の状態は変化せず、unionクエリで変化する状態は定数個(親情報と、rankまたはsizeの情報)なので、「値を変更した配列のインデックスと変更前の値を時刻(クエリ番号)ごとに覚えておく」ことでロールバックが実現できます。

今回の問題の場合は追加で、各連結成分に含まれる  p_{i} の値の集合も持っておきたいです。これは set などで管理しておけば通称マージテクでマージすることができます。このとき「インデックス  iset に値  p を追加した」という情報を記憶しておけば、それを逆に削除することでロールバックできます。

ではこれを利用して前からクエリを処理していきましょう。クエリ2に対しては先ほど解説したロールバックをします。

クエリ1に対しては、その時点での頂点  v のUnion-Findにおける根を求め、その根が持っている set を参照します。ただしこの set には以前のクエリで既に使われている整数が入っている可能性があるため、まず set の中の最大値が使用済みである限りその要素を取り除きます。その上で要素が残っていればその最大値がクエリの答えであり、要素が残っていなければ答えは  0 です。

計算量としては、set の全要素数の合計がマージテクにより  O(n\log n) になるので、その挿入および削除の操作  O(n(\log n)^{2}) が一番重いです。経路圧縮を捨てるとUnion-Findの各クエリが  O(\log n) になるので、全体計算量としては  O(n(\log n)^{2} + (m+q)\log n) になります。

ACコード

set の中で参照する値が最大値だけなので、削除処理を工夫すれば priority_queue でもできます。範囲for文が使えないのが地味に面倒だったりしますが…