CODE FESTIVAL 2016 Final G - Zigzag MST

公式解説とは違う方法で解いたので記録用に残しておきます。

・問題
atcoder.jp
・提出コード
atcoder.jp

最小全域木なので、クラスカルかプリムをしたいですが、流石にクラスカルな気がします。
priority queueに辺を突っ込んで、重みが小さい順にみていくアレですね。
辺の本数が多すぎて、間に合わん模様なので、木に追加する可能性のない辺ははじめからpriority_queueにいれたくないです。

ところで、各クエリ列は2つの部分列に分割することができます。
例えばi番目のクエリ列に関して、それぞれのクエリを辺(頂点1、頂点2、重み)で表すことにすると、
・(A_i,B_i,C_i),(A_i+1,B_i+1,C_i+2),(A_i+2,B_i+2,C_i+4)...
・(A_i+1,B_i,C_i+1),(A_i+2,B_i+1,C_i+3),(A_i+3,B_i+2,C_i+5)...
に分割します。
すると、各分割クエリ列について、各辺(頂点1-頂点2)は定数であり、辺(a,b,w)の次の辺は(a+1,b+1,w+2)になります。

このことより、たとえば辺(a,b,w)を木に追加する必要がないならば(追加しようとするとき既にa,bが連結であるならば)、その次の辺(a+1,b+1,w+2)も追加する必要はがないことがわかります。(1つシフトしているだけなんだから、そらそうよ)

というわけで、priority_queueには、各クエリ列の先頭の辺のみいれてやります。
そして、priority_queueから辺を取り出した際、
・辺(a,b,w)を木に追加する必要があったならば、(a+1,b+1,w+2)を新しくpriority_queueに入れる。
・辺(a,b,w)を木に追加する必要がないならば、(a+1,b+1,w+2)を新しくpriority_queueに入れる。
という流れで、クラスカル法を進めていきます。

すると、priority_queueに入れる辺の本数の合計は、
(はじめに入れる2*Q本)+(木に辺を追加した直後に入れるN-1本)ですから、O(N+Q)です。
合計の計算量は、O( (N+Q)log(N+Q) )になります。