只是在证明前简述了做法，应该不算评论区发题解吧，而且唯一一篇这个复杂度没证明的题解也压在最下面估计没人看。

全是自己口胡的，没写过，应该没假吧。

算法概述

可以容易地感受到 $> \sqrt{n}$ 且 $\leqslant \sqrt{n \log n}$ 的部分用暴力依然有点浪费，$> \sqrt{n \log n}$ 且 $< \sqrt{n} \log n$ 的二分也有点浪费。

令 $a_i$ 为答案 $\geqslant i$ 的 $k$ 右端点，我们考虑从 $a_{i + 1}$ 推出 $a_i$。

类似 finger search，我们在倍增时先不断尝试 $+1, +2, +4, +8, \dots$ 直至失败，然后向下枚举 $2$ 的幂尝试 $\dots, +8, +4, +2, +1$。复杂度为 $\Theta(\log(a_{i + 1} - a_i + 1))$ 次检验与 $\Theta(1)$ 的额外复杂度而无法全部取到 $\Theta(\log n)$。而且可以利用失败的查询做一些优化，这里不赘述（类似 $a_i = a_{i + 1}$ 检验一次后即可跳过后续相同检验，除了这个在 $i > \sqrt{n}$ 的表现之外均为常数优化，注意自上而下二分虽然跑满但若视作一倍常数，finger search 具有两倍常数，复用了信息后应该和整体二分相比只是跳的步长对齐了 $2$ 的幂）。

复杂度证明

因此我们需要的复杂度分析相当于：$a_0 = n, a_{n + 1} = 0, \forall i \in [1, n] \cap \mathbb N, a_i \in [a_{i + 1}, n / i] \cap \mathbb N$，最大化 $\sum_{i = 1}^n \log(a_i - a_{i + 1} + 1)$。

注意到若 $a_i - a_{i + 1} \leqslant a_{i + 1} - a_{i + 2}$ 时交换 $a_i - a_{i + 1}$ 与 $a_{i + 1} - a_{i + 2}$ 仍满足约束且不影响结果，因此不妨假设 $a_i - a_{i + 1} \geqslant a_{i + 1} - a_{i + 2}$。我们可以从 $\forall i \in [1, n] \cap \mathbb N, a_i = \lfloor n / i \rfloor$ 开始，每次对 $a_i - a_{i + 1} \geqslant a_{i + 1} - a_{i + 2} > 0$ 的某个 $i \in [0, n) \cap \mathbb N$ 执行 $a_{i + 1} \leftarrow a_{i + 1} - 1$ 得到任意满足上述约束的 $a$。具体地：

• 注意到 $a_{\left\lfloor \sqrt n \right\rfloor} \leqslant n / \left\lfloor \sqrt n \right\rfloor$，$\sum_{i = \left\lfloor \sqrt n \right\rfloor}^n \log(a_i - a_{i + 1} + 1) = O\left(\sqrt n\right)$。

• 注意到对于 $2 \leqslant x \leqslant y, \log (x - 1) + \log (y + 1) \leqslant \log x + \log y$。

• 注意到 $\int_1^{\sqrt{n}} \log(n / x - n/(x + 1)) \operatorname{d}\! x = \int_1^{\sqrt{n}} \log(n / (x^2 + x)) \operatorname{d}\! x = \Theta\left(\sqrt n\right)$。

洛谷还是有题解是正确的 $\Theta\left(n \sqrt{n}\right)$ 的，只是没写证明：https://www.luogu.com.cn/article/f9wksdt9。整体二分与上述做法本质上基本相同，只是离线后交换了一些检验顺序。