CodeChef March Challenge 2019 - Cheating on Queue

Cheating on Queue (リンク)

問題概要

$A_1, A_2, \dots, A_N$ と $K$ が与えられる。
$i = 1, 2, \dots, N$ に対し $B_i := \lfloor A_i/1 \rfloor + \lfloor A_{i + 1}/2 \rfloor + \dots + \lfloor A_N/(N - i + 1) \rfloor$ としたとき $B_i \le K$ となる最小の $i$ を求めよ。
存在しなければ $N + 1$ を出力する。

$1 \le N \le 10^5$
$1 \le A_i \le 10^5$
$1 \le K \le 10^9$

解法

各 $i$ ごとに $B_i$ を求めるのではなく $A_i$ が $B$ に寄与する量を調べるといいです。
更新はだいたい次のようになります。

$B_1 \gets B_1 + \lfloor A_i/i \rfloor$
$B_2 \gets B_2 + \lfloor A_i/(i - 1) \rfloor$
$\vdots$
$B_{i - 1} \gets B_{i - 1} + \lfloor A_i/2 \rfloor$
$B_i \gets B_i + A_i$

もちろんふつうに計算すると $O(N^2)$ かかるのでダメです。
そこで、たとえば $A_i = 22$ として上の更新式の $+ x$ 部分を見てみます。

Bの添字	i-21	...										...	i-1	i
割る数	22	...	12	11	10	9	8	7	6	5	4	3	2	1
x (商)	1	...	1	2	2	2	2	3	3	4	5	7	11	22

この表から

割る数が小さいうちはふつうに $x$ を足す
大きくなると共通の $x$ が現れる範囲にまとめて足す
- 実際は、範囲の左端に $+x$ して右端に $-x$ しておいてあとで累積和をとります

とすればよさそうと分かります。
割る数を $j$ とおきます。「$j$ の小さいうち」は具体的には $j^2 \le A_i$ 程度にすればいいです。つまり $j \le \lfloor \sqrt{A_i} \rfloor$ です。
また $\lfloor A_i/j \rfloor = x$ となる $j$ の範囲は $(\lfloor A_i / (x + 1) \rfloor, \lfloor A_i / x \rfloor]$ なので添字に変換して $B$ の対応する範囲に $x$ をまとめて足しましょう。
計算量は $O(N \sqrt{\max{A_i}})$ です。