かしのブログ

競技プログラミングとか

第二回アルゴリズム実技検定 N - ビルの建設

AtCoder PAST 平面走査法座標圧縮セグメント木

問題

$N$ 個の敷地（ $i$ 番目の敷地の範囲は $x_i \leq x \leq x_i + D_i, y_i \leq y \leq y_i + D_i$ 、コストは $C_i$ ）がある。座標 $(x, y)$ にあるビルのコストは、その座標を含む敷地のコストの和。 $Q$ 軒のビルのコストを求める。

考察

考える平面が広いので、座標圧縮を行う。以降、圧縮後の座標で考える。

あるビル $j$ のコスト $S_j$ は、以下の式で計算できる。

$S_j = \sum_i \{ C_i\ |\ x_i \leq A_i \leq x_i + D_i \land y_i \leq B_i \leq y_i + D_i\}$

$x, y$ の両方で条件があると難しいので、それぞれの軸で分解する。

$S_j = \sum_{i \in \mathcal{I}} \{ C_i\ |\ y_i \leq B_i \leq y_i + D_i\}$

where $\mathcal{I} = \bigcup_i \{ i\ |\ x_i \leq A_i \leq x_i + D_i\}$

ビルを、 $x$ 座標の小さい方から順に見ていくと、それぞれの $j$ を一回ずつに追加と削除を行うことで $\mathcal{I}$ が得られる。

$y$ 座標についてセグメント木を構築して和を計算できる。

実装