[WUPC] Ramen （WUPC2019 [I]）

概要

問題文 → ■
公式解説 → ■
自分の提出 → ■

解法

問題の言い換え

ある時刻において開店中の店全体の集合を $J$ と書くことにします。次の $3$ 種のクエリを行うことが必要になります。

• 店 $i$ を開店する。
  • $\underset{j\in J}{min}(p_j+|d_i-d_j{|}^2)$ を計算し、$p_i$ を定める。
  • $J$ に $i$ を追加する。
• 店 $i$ を閉店する。
  • $J$ から $i$ を削除する。

$p_i$ の計算には、$\underset{j\in J}{min}(p_j+|d_i-d_j{|}^2)$ が必要となりますが、$f_j(x):=p_j+d_j^2-2d_{j}x$ とすれば、$p_j+|d_i-d_j{|}^2=f_j(d_i)+d_i^2$ なので、$J$ で添字付けられたアフィン関数に対する最小値の計算が欲しいものです。これを行う方法として Convex Hull Trick という有名なテクニックがあり、特に削除クエリがなければ簡単という感じです。

クエリ平方分割による解法（$O(N^{1.5})$ 時間）

$Q=3N$ 件のクエリ処理が要求されています。

適当なバケットサイズ $B$ をとり、$Q$ 件のクエリを $B$ 件のクエリ $\lceil Q/B\rceil$ 回に分けます。次の計算量を目指します。

• あるバケットのクエリ処理の前処理を、 $O(Q)$ 時間で行う
• 個々のクエリを $O(B)$ 時間で処理する

すると、全体の計算量は $O(\lceil Q/B\rceil Q+QB)$ となり、例えば $B=\sqrt{Q}$ ととればこれは $O(Q^{1.5})$ であることが分かります。

---

バケットに対して、次のように処理します。

• クエリ処理の間、常に $J$ に含まれる要素を対象として、Convex Hull Trick の構築を行う
• 各計算クエリに対して、上で追加されたアフィン関数群を対象とした $min$ の計算を行う

全クエリの適当なソート順を（バケット分割よりも前の段階で）事前計算しておけば、直線の追加、計算クエリどちらも何らかの順序にしたがって計算することができ、この工程は $O(Q)$ 時間で行うことができます。

さらに、各計算クエリに対して、次を追加で行います。

• バケット内に追加あるいは削除される直線に対して、計算を行うべきかを判断し、必要ならば計算を行う

計算クエリごとに、バケット内のクエリ全体を愚直に走査して、$O(B)$ 時間で処理することができます。