2/2 日記
今日はめちゃんこおねむにゃん
ぷらにゃをぷにゃぷにゃ
結局、並列二分探索で解けた。
最小全域木を最初に構成し、そこにi番目の辺(u, v)を加えることを考える。
すると、もともと最小全域木に含まれていたu - vパス上の辺のどれか一つを取り除くことができると分かる（図を描くと分かりやすい）。
そのような辺のうち、もっともコストが大きいものを除いたものがクエリ k = i の答えとなる。これをどのようにやるかが問題となるが、最小全域木の構成方法は
「残った辺のうち、連結でない2点を結ぶようなものをコストが小さい順に貪欲に追加していく」どいうものであり、これを利用する。
最小全域木を構成する過程で u と v が連結になったとすると、そのとき加えた辺が取り除くべき辺であることが分かる（追加した辺のうち最もコストが大きく、かつu - v パス上の辺である）。
これをM個やっていては間に合わないため、並列二分探索をする。毎回の操作では最小全域木を構成しながら、途中の段階で u と v が連結であるか判定すればよい。
二次元平面なので、敷地領域の角の座標とビルの建設予定地点を合わせてしまい、x座標でソートして小さい順に見ていけば、あとはy軸方向だけに着目すればよくなる。y~y+DにCを足す（または引く）という操作をしたいので、遅延セグ木を使う。また、座標が-10^9~10^9なので座標圧縮しておく。
i-1番目の項がnowであるとすると、i番目の項の存在範囲が
[ now+1, N-D*(K-i) ] であることが分かる。この範囲で最小値を取る項のうち、最も左に存在するものを選んでいけばいい。最小値はセグ木で求め、後はその値の項が現れるまで順にシミュレートしていけばいい。
考え中。
明日バチャ参加しようかな～
