ABC 401-500/ABC430D - Neighbor Distance - 競技プログラミング用 知識集積所【11/6更新】

---

問題

ABC430D

必要知識

B以下レベルの内容は省略

• 差分更新※
• 二分探索※

考え方

人が何人いても、新たに人を入れたときに「最も近い人までの距離」が変わるのは最大3人（追加した人を含め）しかいない。
よって、差分更新※で処理することで高速化が期待できる。

大きな流れとしては、

• 新たに追加する人の左右隣にいる人の番号を確認する
• 実際に人を追加する
• 自分および左右の人の距離情報を更新
• 3人分を合計値に反映
• 答えを出力

をクエリのたびに繰り返せばよい。

一番実装が大変なのは、左右の人の番号の確認。
実際に人を追加するときに、vectorを実際の並び順に毎回直すのはO(N^2)必要なので不可能。
そこで、これは{位置,番号}のpair型※のset※を作り、挿入前に二分探索※を行い、イテレータを前後に動かすことで確認する。

また、自分が右端だった場合に「右側の人」が存在しないのでここに番兵が欲しく、さらに「右側の人」がこの番兵だと距離情報更新の際に「右側の人の右側の人」がいないのでそれを防ぐ番兵もほしい。
また、0番のすぐ右に入った人の「左側の人の左側の人」も同様に欲しい。
これらの事情と、番兵の距離情報を足してはいけないという面倒な事情を解決するために、20億より右と-10億より左に、同一地点に番兵を2人ずつ計4人置くと実装が楽。
（番兵の距離情報が0になるため、番兵を含めて距離情報を全員分足してしまってよくなる）
もしくは、番兵は「自分の外側の人は自分自身」とすると番兵は2人で済む。

番兵をこれだけ用意すれば、差分更新※は範囲外を気にせずに

• 左右の人の距離情報を引く
• 3人の距離情報を更新して、求めた値を足す

でよい。
また、0番の用意も番兵しかいない場に同じコードで追加すればよい（出力をしないようにだけ注意）。

解答例

解答例

注意点

別解