M - 山分け Editorial by Nachia

別解

Li Chao Tree を用いた解法です。

penguinman さんの公式解説に倣って、 \(a_i := R_i-L_i+1\) とすると、

(海賊 \(l,l+1,\dots,r\) が全員 \(k\) 個以上お宝をもらうことができる)

\[ \begin{aligned} &\iff i=l,l+1,\dots,r \ について \ a_i \geq k(i-l+1) \\ &\iff i=l,l+1,\dots,r \ について \ \frac{i-l+1}{a_i} \leq \frac{1}{k} \\ &\iff \max_{i=l}^{r} \frac{i-l+1}{a_i} \leq \frac{1}{k} \\ &\iff \frac{1}{\max_{i=l}^{r} \frac{i-l+1}{a_i}} \geq k \end{aligned} \]

を得ます。従って、 \((l,r)\) が与えられるクエリの答えは

\[ \left\lfloor \frac{1}{\max_{i=l}^{r} \frac{i-l+1}{a_i}} \right\rfloor \]

と表せます。

\(\frac{i-l+1}{a_i}\)\(l\) の一次関数なので、 Convex Hull Trick を用いて最大値を求めます。

\(f_i(x):=\frac{i-x+1}{a_i}\) とします。

Convex Hull Trick で \(f_i(x)\) \((x \lt i)\)\(i\) の昇順に追加しながら管理すると、 \((l,r) \) が与えられるクエリの答えは \(f_r(x)\) が追加された直後の \(x=l\) における最大値です。

ここで、 \(x \geq i\) のとき \(f_i(x)\leq 0\) であることから、 \(f_i(x)\) を直線として追加してしまっても、管理している直線の \(x \lt i\) の部分に干渉しません。従って、 Convex Hull Trick で必要な操作は直線追加と一点最大値となり、 Li Chao Tree によって時間計算量 \(O((N+Q) \log N)\) が達成されます。

解答例(C++,353ms)

posted:
last update: