CF2173F Isla's Memory Thresholds 题解
Yao_yx
·
·
题解
CF2173F Isla's Memory Thresholds
首先考虑一个朴素的做法。从 $l$ 到 $r$ 每次二分处下一次的长度，然后再二分该长度的出现次数。由于本质不同的长度只有 $O(\sqrt n)$ 个，时间复杂度 $O(n\sqrt n\log n)$。卡常后可以通过。
考虑优化。首先要知道一种 $O(\log ans)$ 的二分答案，其中 $ans$ 是最终二分出来的答案。这个叫做指数搜索（exponential search）。具体来说，由于答案具有单调性，故存在一个断点满足断点之前的满足条件，断点之后的不满足条件。于是先倍增，也就是先 check $2^0,2^1,2^2,\dots$ 的位置是否满足条件，直到找到一个 $k$ 使得 $2^k$ 满足条件且 $2^{k+1}$ 不满足条件。这样就能确定 $ans\in[2^k,2^{k+1})$ 了，于是最后再在 $[2^k,2^{k+1})$ 二分 $ans$。容易发现这样是 $O(\log ans)$ 的，但是带两倍常数。
所以就将上述二分答案改为指数搜索。下面证明该算法复杂度是 $O(\sqrt n)$ 的。
首先假设所有选择的长度为 $a_1<a_2<\dots<a_m$，各出现了 $b_1,b_2,\dots,b_m$ 次。则满足 $a_1b_1+a_2b_2+\dots+a_mb_m\le n$。因此只需证明 $a_1b_1+a_2b_2+\dots+a_mb_m=n$ 的情况即可。发现贡献为 $\sum\limits_{i=1}^m(\log_2(a_i-a_{i-1})+\log_2b_i)$。第一个 $\log$ 是因为每次要找下一次的长度，可以从上一次的长度开始找。第二个 $\log$ 显然是因为要二分次数。
考虑分别证明 $O(\sum\limits_{i=1}^m\log_2(a_i-a_{i-1}))$ 和$O(\sum\limits_{i=1}^m\log_2b_i)$ 的最大上界是 $O(\sqrt n)$。对于第一个证明，发现条件等价与 $a_1+a_2+\dots+a_m=n-a_1(b_1-1)-a_2(b_2-1)-\dots-a_m(b_m-1)$，所以只需考虑 $b_i=1$ 的情况，不然问题被缩小到更小的规模肯定不优。对于第二个证明，容易发现 $a_i$ 最小时 $O(\sum\limits_{i=1}^m\log_2b_i)$ 才能取到最大值。由于 $a_i\ge i$，故只需证明 $b_1+2b_2+\dots+mb_m=n$ 的情况。
对于第一种情况：给定正整数数组 $a$ 满足 $a_1<a_2<\dots< a_m$ 且 $a_1+a_2+\dots+a_m=n$。证明 $O(\sum\limits_{i=1}^m\log_2(a_i-a_{i-1}))$ 的最大上界为 $O(\sqrt n)$。
记 $d_i=a_i-a_{i-1}$。则 $a_1+a_2+\dots+a_m=n$ 等价于 $\sum\limits_{i=1}^m\sum\limits_{j=1}^id_j=n$，也就是 $\sum\limits_{i=1}^m(m-i+1)d_i=n$。现在要求 $O(\sum\limits_{i=1}^m\log_2(a_i-a_{i-1}))=O(\sum\limits_{i=1}^m\log_2d_i)$ 的最大上界。
考虑使用拉格朗日乘数法。构造拉格朗日函数 $L(d_1,d_2,\dots,d_m,\lambda)$ 满足：
$$L(d_1,d_2,\dots,d_m,\lambda)=\sum\limits_{i=1}^m\log_2d_i-\lambda(\sum\limits_{i=1}^m(m-i+1)d_i-n)$$
对每个 $d_i$ 求偏导：
$$\frac{\partial L}{\partial d_i}=\frac{1}{d_i\ln2}-\lambda(m-i+1)=0\\d_i=\frac{1}{\lambda(m-i+1)\ln2}$$
带入约束条件：
$$\sum_{i=1}^m(m-i+1)\frac{1}{\lambda(m-i+1)\ln2}=\sum_{i=1}^m\frac{1}{\lambda\ln2}=\frac{m}{\lambda\ln2}=n$$
解得 $\lambda=\dfrac{m}{n\ln2}$，故 $d_i=\dfrac{n}{m(m-i+1)}$。
因此 $\sum\limits_{i=1}^m\log_2d_i=\sum\limits_{i=1}^m\log_2\dfrac{n}{m(m-i+1)}=\sum\limits_{i=1}^m(\log_2n-\log_2m-\log_2(m-i+1))=m\log_2n-m\log_2m-\sum\limits_{i=1}^m\log_2(m-i+1)=m\log_2n-m\log_2m-\log_2(m!)=O(m\log n-m\log m-\log(m!))$。
根据斯特林公式，$\log(m!)=m\log m-m+O(\log m)$，故 $O(\sum\limits_{i=1}^m\log d_i)=O(m\log n-2m\log m+m)$。
视 $m$ 为变量，$n$ 为常量。等价于要求 $f(m)=m\log n-2m\log m+m$。求导得：$f^\prime(m)=\log n-2\log m-2+1=\log n-2\log m-1$。令导数为 $0$ 并以 $2$ 为底，可解得 $m=\sqrt\dfrac{n}{2}$，带回 $f(m)=2\sqrt\dfrac{n}{2}$。综上，$O(\sum\limits_{i=1}^m\log_2d_i)$ 的最大上界为 $O(\sqrt n)$。
对于第二个证明：给定正整数数组 $b$ 满足 $b_1+2b_2+\dots+mb_m=n$。证明 $O(\sum\limits_{i=1}^m\log_2b_i)$ 的最大上界为 $O(\sqrt n)$。
先使用 AM-GM 不等式。即 $\dfrac{b_1+2b_2+\dots+mb_m}{m}\ge\sqrt[m]{b_1\cdot2b_2\cdot\dots\cdot mb_m}$，化简得 $\prod\limits_{i=1}^mb_i\le(\frac{n}{m})^m\frac{1}{m!}$，所以 $\sum\limits_{i=1}^m\log_2b_i\le m\log_2n-m\log_2m-\log_2(m!)$。这和上面的式子是一模一样的，还是使用斯特林公式可以证明复杂度为 $O(\sqrt n)$。
综上，总时间复杂度 $O(\sqrt n)$。
[code](https://codeforces.com/contest/2173/submission/352110878)（放了别人的代码，又快又很简洁）。