题解：CF2173F Isla's Memory Thresholds

· · 题解

首先有一个显然的 \mathcal O(n\sqrt n\log n) 或者 \mathcal O(n\sqrt{n\log n}) 的暴力（事实上写一下就直接过了）。

由于 a_i 不增，所以每次凑到 x 所需要的区间长度是不降的。

我们初始只走长度为 1 的区间，每一次先二分出这样的区间可以走几步。

然后我们二分下一次需要的区间长度。

这样可以轻松做到 \mathcal O(n\sqrt n\log n)。稍微编个优化比如步长 \leq \sqrt n 的时候预处理一下之类的，就可以调整一下块长做到 \mathcal O(n\sqrt{n\log n})。

接下来将会介绍本题 \mathcal O(n\sqrt n) 做法（与值域无关）。

引理 1：对于正整数数列 a_1,a_2,\dots,a_k，且满足 \sum a_i\times i\leq n，则 \sum \log(a_i) 是 \mathcal O(\sqrt n) 级别的。

引理 2：对于正整数数列 b_1,b_2,\dots,b_k，且满足 \sum b_i\leq n，则 \sum \log(b_{i+1}-b_i) 是 \mathcal O(\sqrt n) 级别的。

感性理解一下，由于 \log(x) 的导函数，在第一象限单调递减，所以引理 1 中我们让 a_i 尽量是 2 比较好。那么 i 取到前 \mathcal O(\sqrt n) 个正整数。

同理，在引理 2 中，我们尽量让 b_{i+1}-b_i=2，那么构造出来也只有 \mathcal O(\sqrt n) 项，所以是 \mathcal O(\sqrt n) 的。

引理 1，告诉我们的是，『二分出这样的区间可以走几步』的二分过程是 \mathcal O(\sqrt n) 的，引理 2，告诉我们的是，『二分下一次需要的区间长度』的二分过程是 \mathcal O(\sqrt n) 的。当然，前提是我们知道了 \boldsymbol{a_i} 和 \boldsymbol{b_{i+1}-b_i} 的量级，而不能每次都二分右端点当成 n。

为了找到正确的引理 1 的 a_i 和引理 2 的 b_{i+1}-b_i 量级，我们考虑这样一个过程：先枚举 k 使得 2^{k-1} 合法但是 2^k 不合法，这就说明答案出现在 [2^{k-1},2^k)。我们在这个区间内二分即可。

这样每次枚举的 k 和 \log(a_i) 是一个量级的，那么就可以通过上述引理的分析，将本题做法优化到 \mathcal O(n\sqrt n)。