整数値を取り $f(k) \le n/k$ のように制約され単調減少する $f$ に対して、普通にひとつ計算すると $O(g(n))$ かかるところを $f(1),f(2),\dots,f(n)$ をまとめて $O(g(n) \sqrt{n} \log{n})$ で計算するテク

Problem - D - Codeforces (CFR507-D1D) に使いました

以下の条件を満たす $f$ を取り扱います。

• $f$ は整数値を取る
• $f(k) \le N/k$ のように制約される ( $n$ 個のものをどうにかして $k$ 個ずつ個包装したい場合など… )
• $f$ は(広義)単調減少する

$f$ を普通にひとつ計算すると $O(g(n))$ かかるとしましょう。この時、以下の手順で $f(1),f(2),\dots,f(n)$ をまとめて $O(g(n) \sqrt{n} \log{n})$ で計算できます。

まず、 $f(1)$ と $f(n)$ を普通に計算する。

次に、以下の分割統治を定義する。

• [ $l,f(l),r,f(r)$ ] の値を渡しながら再帰的に解く。ここでは $f(l)$ から $f(r)$ までを管理する。
• $l+1 \ge r$ ならば続行する意味が無いので終了。
• $f(l)=f(r)$ ならば $f(l)=f(l+1)= \dots =f(r)$ が判明して終了。
• $m = \lfloor \frac{l+r}{2} \rfloor$ とし、 $f(m)$ を求める。
• 最後に、以下のふたつを呼ぶ。
  • [ $l,f(l),m,f(m)$ ]
  • [ $m,f(m),r,f(r)$ ]

これで [ $1,f(1),n,f(n)$ ] を呼べば目的達成。

ざっくりした計算量の証明:

$f$ は整数値を取り、その値の種類数は $O(\sqrt{n})$ である。この全部について $f$ がある値以上か未満かの二分探索をすることを考えるが、これでアクセスする部分には上の分割統治でもアクセスされ、アクセスされない部分にはアクセスされないはずである。なので $O(\log n)$ が掛かって全体で $O(g(n))$ を $O(\sqrt{n} \log{n})$ 回呼ぶことになる。

最初に挙げた問題での実装例: Submission #227612376 - Codeforces

ばちゃ中に再発明したけど違う方も同じことやってるコード書いてたし実はけっこう有名そう。もっといい名前とか付いてるのかな