题解：P10428 [蓝桥杯 2024 省 B] 爬山
chen_zhe
·
2026-09-10 16:52:14
·
题解
题意简述
给定 n 个非负整数 h_i ，可以使用至多 P 次向下取整的开方，以及至多 Q 次向下取整的除以二。每个数可以接受多次操作，顺序不限，求最终的最小总和。
记 H=\max h_i 。下面给出时间复杂度为 O(n+H\log(H+1)) 、空间复杂度为 O(H) 的做法，并证明它为什么能够处理两种操作次数的限制。
思路
先确定操作顺序，再给除以二附加代价
记 A(x)=\lfloor\sqrt x\rfloor ，B(x)=\lfloor x/2\rfloor 。由于 B(A(x))\le A(B(x)) ，把相邻的“先除以二、后开方”交换后，高度不会增大。两种操作又都单调不减，因此后续操作也不会破坏这个结论。不断交换，就能让每座山先做完所有开方，再做除以二。
不过，开方应该分配给哪些山，仍然受到除以二次数的影响。例如高度为 9,8 ，两种操作各一次时，对 9 开方得到的最小总和是 7 ，对 8 开方却能得到 6 。所以不能直接对当前最高的山使用开方。
我们先保留开方次数的限制，暂时取消除以二的次数限制，改为每用一次除以二，就在答案中额外加入代价 w 。固定整数 w\ge1 ，定义
F_w(x)=\min_{b\ge0}\left(\left\lfloor\frac{x}{2^b}\right\rfloor+wb\right).
它表示高度为 x 的山只使用除以二时，“最终高度加操作代价”的最小值。按照是否进行第一次操作，可以得到 F_w(0)=0 ，并对 x\ge1 写出
F_w(x)=\min\left(x,\ w+F_w\left(\left\lfloor\frac{x}{2}\right\rfloor\right)\right).
因此，固定 w 后，可以按高度递增，在 O(H) 时间内算出所有 F_w(x) 。
还要记录取得最小值时，最少和最多使用多少次除以二，分别记为 L_w(x),R_w(x) 。当前高度为 t 时，再除以二一次降低 \lceil t/2\rceil ，这些降低量随操作次数单调不增。因此，取得最小值的次数恰好构成完整整数区间 [L_w(x),R_w(x)] 。选择最少次数时，只做收益严格大于 w 的操作，所以
L_w(x)=\min\left\{b\ge0:\left\lfloor\frac{x}{2^b}\right\rfloor\le2w\right\}.
这两个端点也能与 F_w 一起递推。如果除以二后的代价严格更小，就继承子状态的两个端点并加一；如果代价相等，最少次数为 0 ，最多次数继承子状态后加一。
设整个附加代价问题的最优值为 G(w) ，最优方案中除以二次数的两个端点为 q_{\min}(w),q_{\max}(w) 。接下来需要解决两件事：先求出这三个量，再证明可以找到一个代价，使某个最优方案恰好使用 Q 次除以二。
固定代价后，按开方收益选取
对一座山开方一次，相当于将后续除以二的最优代价从 F_w(x) 降为 F_w(A(x)) 。因此定义这次开方的收益，以及它对次数端点的影响：
\begin{aligned}
D_w(x)&=F_w(x)-F_w(A(x)),\\
K^-_w(x)&=L_w(x)-L_w(A(x)),\\
K^+_w(x)&=R_w(x)-R_w(A(x)).
\end{aligned}
每座山的连续开方产生一条链 h_i\to A(h_i)\to A^2(h_i)\to\cdots ，选取的步骤必须构成前缀。如果这条链上的收益单调不增，就能从所有链中选取最大的 P 个收益。为了同时求出次数端点，还需要证明相等收益下的排序不会破坏前缀限制。
以下在固定 w 时省略下标。记 \rho(z)=\lfloor z/2^{L(z)}\rfloor ，也就是做完最少最优次数后剩下的高度。对正整数 z ，有 1\le\rho(z)\le2w ；如果 L(z)>0 ，最后一次操作前的高度大于 2w ，所以还满足 \rho(z)\ge w 。另外，若 \rho(z)=2w ，再除以二的收益恰好等于代价，因此 R(z)\ge L(z)+1 。
先证明：对整数 w\ge2 、s\ge2 ，有 F_w(s^2)\ge2F_w(s) 。取 b=L_w(s^2) ，做完这些操作后的高度至少为 2 。
如果 b=2a+1 ，令 u=\lfloor s/2^a\rfloor 。由 \lfloor u^2/2\rfloor+2\ge2u ，得到
\begin{aligned}
F_w(s^2)
&\ge\left\lfloor\frac{u^2}{2}\right\rfloor+(2a+1)w\\
&\ge2u+2aw\\
&\ge2F_w(s).
\end{aligned}
如果 b=2a ，仍令 u=\lfloor s/2^a\rfloor 。当 u\ge2 时，由 u^2\ge2u 得
F_w(s^2)\ge u^2+2aw\ge2(u+aw)\ge2F_w(s).
最终高度至少为 2 ，所以 u=0 不可能。若 u=1 ，则 a\ge1 ，令 v=\lfloor s/2^{a-1}\rfloor ，有 v\in\{2,3\} 。这两个值均满足 \lfloor v^2/4\rfloor+2w\ge2v ，所以
F_w(s^2)
\ge\left\lfloor\frac{v^2}{4}\right\rfloor+2aw
\ge2\bigl(v+(a-1)w\bigr)
\ge2F_w(s).
平方不等式得证。现在令 s=A(x)\ge2 。因为 F_w 单调不减，且 x\ge s^2 ，所以
\begin{aligned}
D_w(x)
&\ge F_w(s^2)-F_w(s)\\
&\ge F_w(s)\\
&>F_w(s)-F_w(A(s))\\
&=D_w(s).
\end{aligned}
最后一个严格不等式来自 A(s)\ge1 ，从而 F_w(A(s))>0 。因此，当 w\ge2 时，相邻两次有效开方的收益严格递减。
当 w=1 时，由递推式可归纳得到：对正整数 z ，F_1(z)=R_1(z)=\lfloor\log_2z\rfloor+1 。若 x 的二进制位数为 m ，则 A(x) 的位数为 \lceil m/2\rceil ，所以 D_1(x)=\lfloor m/2\rfloor 。相邻两次有效开方收益相等，只会出现在 x\in\{4,5,6,7\} ，对应 x\to2\to1 。此时，第一次的 K^- 为 1 或 2 ，第二次为 0 ；两次的 K^+ 都为 1 。
因此，对所有整数 w\ge1 ，沿开方链，二元组 (D,K^-) 和 (D,-K^+) 都按字典序单调不增。忽略高度 0,1 上的无效开方后，其余步骤的收益均为正，选取最大的 P 个收益即可；有效步骤不足 P 个时全部选取。
求 q_{\min} 时，初始次数为 \sum_iL_w(h_i) ，每选一步就减去对应的 K^- ，所以收益相等时应优先选 K^- 大的。求 q_{\max} 时，初始次数为 \sum_iR_w(h_i) ，每选一步减去 K^+ ，所以应优先选 K^+ 小的。上面的链上单调性保证这两个排序都合法，从而可以分别求出 G(w),q_{\min}(w),q_{\max}(w) 。
比较开方收益与节省的除法次数
只知道最少、最多次数还不够。如果两者之间缺少某些整数，或者必须取非整数代价才能得到所需次数，就不能直接做整数二分。为了解决这两个问题，下面证明同一个关键性质：
K^-(x)\ge K^-(y)+2
\quad\Longrightarrow\quad
D(x)\ge D(y).
\tag{1}
这里固定整数 w\ge1 ，且 x,y\ge2 。也就是说，如果一次开方至少多节省两次除以二，那么它的收益不会更小。我们还会证明：收益相等时，必有
\begin{gathered}
K^-(x)=K^-(y)+2,\\
\rho(x)=w,\qquad \rho(A(x))=2w,\\
\rho(y)=2w,\qquad \rho(A(y))=w.
\end{gathered}
\tag{2}
对 z\in\{x,y\} ，记 k_z=K^-(z) 、u_z=\rho(z) 、v_z=\rho(A(z)) 。于是 D(z)=wk_z+u_z-v_z 。由于 L 单调不减，k_z\ge0 ；又因为 k_x\ge k_y+2 ，所以 L(x)\ge2 ，进而 u_x\ge w 。
若 v_y\ge w ，直接利用剩余高度的范围，有
\begin{aligned}
D(x)-D(y)
&=w(k_x-k_y)+u_x-v_x-u_y+v_y\\
&\ge w(k_x-k_y)-2w\\
&\ge0.
\end{aligned}
只有 k_x-k_y=2 、u_x=w 、v_x=2w 、u_y=2w 、v_y=w 时可能取等，正好得到式 (2) 。
下面处理 v_y<w 。这时 L(A(y))=0 ，令 a=A(y)=v_y ，有 1\le a<w 。如果 u_y<w ，则 L(y)=k_y=0 ，所以 D(y)=u_y-a<w ；而 D(x)\ge w(k_x-1)\ge w ，严格不等式成立。
以下设 u_y\ge w 。如果 k_x-k_y\ge3 ，则 D(x)-D(y)\ge w(k_x-k_y)-3w+1\ge1 。故只需讨论 k_x=k_y+2 。
剩下 $w\ge3$。令 $T=2^{k_y}$、$u=u_x$、$v=u_y$、$j=L(A(x))$，其中 $w\le u,v\le2w$。因为 $L(y)=k_y$，有 $Tv\le y<(a+1)^2$。又因为 $L(x)=j+k_y+2$，有
$$
(2^jv_x)^2\le A(x)^2\le x<2^{j+k_y+2}(u+1),
$$
所以 $v_x<2\sqrt{T(u+1)}$。结合 $Tv<(a+1)^2$ 和 $a+1\le w$，得到
$$
\begin{aligned}
v_x-a
&<2(a+1)\sqrt{\frac{u+1}{v}}-a\\
&=(a+1)\left(2\sqrt{\frac{u+1}{v}}-1\right)+1\\
&\le w\left(2\sqrt{\frac{u+1}{v}}-1\right)+1.
\end{aligned}
\tag{3}
$$
最后一步的括号为正，因为 $(u+1)/v>1/2$。接下来使用 $2\sqrt t\le t+1$，有
$$
\begin{aligned}
3w+u-v-2w\sqrt{\frac{u+1}{v}}
&\ge2w+u-v-\frac{w(u+1)}v\\
&=\frac{w-1}{2}
+\frac{(2w-v)(2v-w-1)}{2v}
+\frac{(u-w)(v-w)}v\\
&\ge\frac{w-1}{2}\\
&\ge1.
\end{aligned}
\tag{4}
$$
由式 $(3),(4)$，得到 $v_x-a<2w+u-v$。因此 $D(x)-D(y)=2w+u-v-(v_x-a)>0$。这就证明了式 $(1)$，也证明了收益相等时只能出现式 $(2)$ 的情况。
#### 恢复除以二的次数限制
先证明最优次数之间没有缺失整数。假设 $D(x)=D(y)$，我们需要比较“对 $x$ 开方”和“对 $y$ 开方”这两种选择。
如果 $K^-(x)\le K^-(y)+1$，由 $R\ge L$ 可得
$$
L(x)+L(A(y))\le R(A(x))+R(y)+1.
\tag{5}
$$
否则，根据式 $(1),(2)$，必有 $K^-(x)=K^-(y)+2$，且 $\rho(A(x))=\rho(y)=2w$。这意味着 $R(A(x))\ge L(A(x))+1$、$R(y)\ge L(y)+1$，式 $(5)$ 仍然成立。
对 $x$ 开方时，这两座山的最优除以二次数区间为 $[L(A(x))+L(y),R(A(x))+R(y)]$；对 $y$ 开方时，区间为 $[L(x)+L(A(y)),R(x)+R(A(y))]$。式 $(5)$ 以及交换 $x,y$ 后的版本，保证两个区间相交或相邻，中间没有缺失整数。加上其他山的次数区间后，结论也不变。
固定代价后，最优开方方案选完所有大于临界收益的步骤，只在等于临界收益的步骤中分配剩余名额。任意两个这样的前缀方案，都能通过相等收益的交换相互到达：每次从一条比目标方案多选的链中删除最后一个已选步骤，再向一条少选的链中加入第一个未选步骤。这个过程始终保持前缀合法，并逐步到达目标方案。
固定开方方案对应一个完整整数次数区间，相邻方案的区间又相交或相邻，所以所有最优方案对应的次数恰好构成完整整数区间 $[q_{\min}(w),q_{\max}(w)]$。不需要选开方或选完所有有效开方时，开方方案只有一种，结论同样成立。
接下来证明只考虑整数代价就足够。如果 $D_w(x)<D_w(y)$，式 $(1)$ 推出 $K^-_w(x)\le K^-_w(y)+1$。由于收益为整数，所以
$$
D_w(x)+K^-_w(x)\le D_w(y)+K^-_w(y).
\tag{6}
$$
每次除以二的收益都是整数，因此，当实数代价 $\lambda\in(w,w+1)$ 时，一座山的最优次数固定为 $L_w(z)$，从而
$$
\begin{aligned}
F_\lambda(z)&=F_w(z)+(\lambda-w)L_w(z),\\
D_\lambda(z)&=D_w(z)+(\lambda-w)K^-_w(z).
\end{aligned}
$$
式 $(6)$ 保证左端点处严格有序的收益，到右端点也不会反序；它们都是线性函数，因此在开区间内不会反转。左端点处相等的收益，在开区间内按 $K^-$ 排序，顺序也固定。因此，每个相邻整数代价之间，都存在固定的合法贪心顺序，$G(\lambda)$ 在该区间上是线性的。
每个固定方案的“最终高度和加操作代价”都是关于 $\lambda$ 的直线，斜率就是除以二次数，而 $G(\lambda)$ 是这些直线的最小值。因此它是凹分段线性函数。在整数 $w$ 处，向右稍微增加代价，相等的最优方案中使用次数最少的更优；向左稍微减少代价，使用次数最多的更优。所以右斜率为 $q_{\min}(w)$，左斜率为 $q_{\max}(w)$。相邻整数之间没有折点，便有 $q_{\min}(w)=q_{\max}(w+1)$，且最优次数随代价增加而单调不增。
现在就可以进行整数二分。先处理答案为零的情况：当 $w=1$ 时，$F_1(z)=R_1(z)$，选择最大最优次数会将山降为零。因此 $q_{\max}(1)=G(1)$，若 $Q\ge q_{\max}(1)$，直接输出 $0$。
否则，二分最小的满足 $q_{\min}(w)\le Q$ 的整数 $w$。如果 $w=1$，已有 $Q<q_{\max}(1)$；如果 $w>1$，根据最小性，$q_{\max}(w)=q_{\min}(w-1)>Q$。所以一定有 $q_{\min}(w)\le Q\le q_{\max}(w)$，而前面已经证明区间内每个整数都能取得。这就找到了一个达到 $G(w)$、恰好使用 $Q$ 次除以二的方案。
任意原问题合法方案，若最终高度和为 $S$，使用了 $b\le Q$ 次除以二，那么 $G(w)\le S+wb\le S+wQ$，所以 $S\ge G(w)-wQ$。上面找到的方案恰好取等，最终答案就是
$$
\boxed{\operatorname{OPT}(Q)=G(w)-wQ}.
$$
#### 用计数桶完成每次计算
前面的证明给出了排序贪心，但实现时不必真的存储、排序每座山的开方链。由于高度和收益都不超过 $H$，可以使用计数桶。
令 $\mathrm{freq}[x]$ 表示初始高度为 $x$ 的山的数量，$\mathrm{cnt}[x]$ 表示所有开方链中，步骤 $x\to A(x)$ 出现的总次数。先令 $\mathrm{cnt}=\mathrm{freq}$，再按高度从大到小，对每个 $x\ge2$ 将 $\mathrm{cnt}[x]$ 加到 $\mathrm{cnt}[A(x)]$。因为 $A(x)<x$，处理 $x$ 时，所有会到达 $x$ 的链已经统计完整。高度 $0,1$ 上的开方没有作用，不计入有效步骤；如果有效步骤总数不足 $P$，将 $P$ 截断到该总数。
固定 $w$ 后，先递推所有 $F_w,L_w,R_w$，并统计不开方时的总代价和两个次数端点。接着把 $\mathrm{cnt}[x]$ 个收益 $D_w(x)$ 加入对应的桶，从大到小找到第 $P$ 大收益 $\mathrm{cut}$。
收益大于 $\mathrm{cut}$ 的步骤全部选取，直接扣除它们的收益和次数变化。收益等于 $\mathrm{cut}$ 的步骤，只需再选择剩余名额：求最少次数时按 $K^-$ 从大到小选，求最多次数时按 $K^+$ 从小到大选。这两次选择可以得到不同的开方方案，但总代价相同，分别对应所需的两个端点。
由于 $h_i\le10^5$，至多除以二 $17$ 次就会变为 $0$，所以 $K^-,K^+$ 都在 $[0,17]$ 内，临界收益上的选择也可以用小桶完成。这样，一次计算只需 $O(H)$ 时间。
二分范围取 $[1,H+1]$。当代价为 $H+1$ 时，任何一次除以二都不划算，最优次数必为 $0$，因此右端点一定满足二分条件。$P=0$ 时直接跳过开方收益的选取；所有高度为 $0$ 时，在代价为 $1$ 的检查中就会返回零。总高度可能达到 $10^{10}$，总代价、次数汇总和最终答案均使用 `long long`。
### 复杂度分析
设 $H=\max h_i$。读取输入和预处理开方链计数需要 $O(n+H)$ 时间；每个整数代价下，递推和计数桶贪心需要 $O(H)$ 时间；二分需要 $O(\log(H+1))$ 次计算。
因此，总时间复杂度为 $O(n+H\log(H+1))$，空间复杂度为 $O(H)$。
### 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Result {
ll val, qmin, qmax;
};
struct Solver {
int H, P;
vector<int> rt, freq, cnt, f, bmin, bmax, bucket;
Solver(const vector<int>& h, int p) : P(p) {
H = *max_element(h.begin(), h.end());
rt.resize(H + 1);
freq.assign(H + 1, 0);
for (int x : h) ++freq[x];
for (int x = 1; x <= H; ++x) {
rt[x] = rt[x - 1];
if ((rt[x] + 1) * (rt[x] + 1) <= x) ++rt[x];
}
// cnt[x] 记录所有开方链中 x -> sqrt(x) 这一步出现的总次数。
cnt = freq;
int total = 0;
for (int x = H; x >= 2; --x) {
total += cnt[x];
cnt[rt[x]] += cnt[x];
}
P = min(P, total);
f.resize(H + 1);
bmin.resize(H + 1);
bmax.resize(H + 1);
bucket.resize(H + 1);
}
// 返回 G(w)，以及最优方案中除以二次数的最小值和最大值。
Result calc(int w) {
fill(bucket.begin(), bucket.end(), 0);
Result res{0, 0, 0};
for (int x = 0; x <= H; ++x) {
f[x] = x;
bmin[x] = bmax[x] = 0;
if (x && w + f[x / 2] <= x) {
f[x] = w + f[x / 2];
bmax[x] = bmax[x / 2] + 1;
if (f[x] < x) bmin[x] = bmin[x / 2] + 1;
}
res.val += 1LL * freq[x] * f[x];
res.qmin += 1LL * freq[x] * bmin[x];
res.qmax += 1LL * freq[x] * bmax[x];
}
if (!P) return res;
for (int x = 2; x <= H; ++x)
bucket[f[x] - f[rt[x]]] += cnt[x];
int cut = H, need = P;
while (bucket[cut] < need) need -= bucket[cut--];
// 收益大于 cut 的全部选取，等于 cut 的再选 need 个。
// h <= 100000，至多 17 次除以二就会变为 0。
vector<int> low(18, 0), high(18, 0);
for (int x = 2; x <= H; ++x) {
int y = rt[x], d = f[x] - f[y];
if (d > cut) {
res.val -= 1LL * cnt[x] * d;
res.qmin -= 1LL * cnt[x] * (bmin[x] - bmin[y]);
res.qmax -= 1LL * cnt[x] * (bmax[x] - bmax[y]);
} else if (d == cut) {
low[bmin[x] - bmin[y]] += cnt[x];
high[bmax[x] - bmax[y]] += cnt[x];
}
}
res.val -= 1LL * need * cut;
int left = need;
for (int k = 17; k >= 0; --k) {
int take = min(left, low[k]);
res.qmin -= 1LL * take * k;
left -= take;
}
left = need;
for (int k = 0; k <= 17; ++k) {
int take = min(left, high[k]);
res.qmax -= 1LL * take * k;
left -= take;
}
return res;
}
ll solve(int Q) {
Result first = calc(1);
if (Q >= first.qmax) return 0;
int l = 1, r = H + 1;
while (l < r) {
int mid = (l + r) / 2;
if (calc(mid).qmin <= Q) r = mid;
else l = mid + 1;
}
Result res = calc(l);
return res.val - 1LL * l * Q;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, P, Q;
cin >> n >> P >> Q;
vector<int> h(n);
for (int& x : h) cin >> x;
cout << Solver(h, P).solve(Q) << '\n';
return 0;
}
```
---
以为到这里就结束了吗，嘿嘿错了，[nmsy 提出的优化方案](https://www.luogu.com/paste/i5xip8mv)。
仍记 $H=\max h_i$、$A(x)=\lfloor\sqrt x\rfloor$，并沿用前文的 $F_w,L_w,D_w,G,q_{\min}$。本节只计算最少除法次数，因此将 $K^-_w(x)$ 简记为 $K_w(x)=L_w(x)-L_w(A(x))$。前文已经证明，从所有有效开方步骤中按 $(D_w,K_w)$ 的字典序选取最大的 $P$ 份，就能同时得到 $G(w)$ 和 $q_{\min}(w)$；并且这样的选取可以满足每条开方链的前缀限制。
二分与还原答案也沿用前文结论：若 $Q\ge G(1)$，答案为 $0$；否则找到最小的、满足 $q_{\min}(w)\le Q$ 的整数 $w$，答案就是 $G(w)-wQ$。因此，优化版不必再维护 $q_{\max}$。
### 先把固定高度分布的询问做到常数时间
暂时固定所有山的高度，只考虑除以二。某一步从 $x$ 变为 $\lfloor x/2\rfloor$，降低的高度为 $\lceil x/2\rceil$。一条除法链上的降低量单调不增，所以在每步附加代价 $w$ 后，要在最优值相同的情况下尽量少用操作，就应恰好选取降低量严格大于 $w$ 的步骤。
可以一次统计所有除法链上的降低量。令 $c[x]$ 初始为高度 $x$ 的山的数量，按 $x$ 从大到小处理：先将 $c[x]$ 加入降低量 $\lceil x/2\rceil$ 的计数，再把 $c[x]$ 加到 $c[\lfloor x/2\rfloor]$。每个高度只处理一次，花费 $O(H)$ 时间。将所得计数做后缀和，记 $T(w)$ 为降低量大于 $w$ 的步骤数，$U(w)$ 为这些步骤降低量的总和。若这份固定分布的原始高度和为 $S$，则一次询问的结果为
$$
\begin{aligned}
V(w)&=S-U(w)+wT(w),\\
q_{\min}^{\mathrm{fixed}}(w)&=T(w).
\end{aligned}
$$
后缀数组直接访问下标 $w+1$，所以询问只需 $O(1)$ 时间。代码中的 `HalfTable` 就负责这部分。后面会为原始高度分布，以及预先选好一组开方步骤后的高度分布，各建一张表。
我们还需要在 $O(1)$ 时间内查询单个高度的 $F_w(x),L_w(x)$。第 $b$ 次除法的收益严格大于 $w$，等价于操作前的高度至少为 $2w+1$，也就等价于 $x\ge(2w+1)2^{b-1}$。定义 $\operatorname{bitlen}(t)$ 为非负整数 $t$ 的二进制位数，并约定 $\operatorname{bitlen}(0)=0$，于是
$$
\begin{aligned}
L_w(x)&=\operatorname{bitlen}\left(\left\lfloor\frac{x}{2w+1}\right\rfloor\right),\\
F_w(x)&=\left\lfloor\frac{x}{2^{L_w(x)}}\right\rfloor+wL_w(x).
\end{aligned}
$$
用 $\operatorname{bitlen}(t)=\operatorname{bitlen}(\lfloor t/2\rfloor)+1$ 预处理位数表，再预处理整数平方根表，就能在常数时间内得到 $(D_w(x),K_w(x))$。这里不能对每个高度再循环模拟除法，否则会多出一个对数因子。
最后，沿用原算法对开方链的统计：令 `cnt[x]` 初始为原始高度频率，按 $x$ 从大到小，将 `cnt[x]` 加到 `cnt[A(x)]`，只处理 $x\ge2$。这样 `cnt[x]` 就是起始高度为 $x$ 的有效开方步骤数。再做前缀和 $C(t)=\sum_{x=2}^t\mathrm{cnt}[x]$，即可用 $C(r)-C(l-1)$ 查询任意高度区间包含多少份开方步骤。
### 代价较小时，跳过关键字不变的区间
考虑 $1\le w<\lceil\sqrt H\rceil$。不再逐一枚举高度，而是一次处理一段具有相同 $(D_w,K_w)$ 的高度。由于同一段中的步骤完全等价，我们只需用前缀和求出它们的总份数。
设当前扫描到 $x$，记 $s=A(x)$、$a=2w+1$、$\ell=L_w(x)$、$m=L_w(s)$。当 $\ell,m,\lfloor x/2^\ell\rfloor,\lfloor s/2^m\rfloor$ 都不变时，$D_w(x)$ 和 $K_w(x)$ 也都不变。前两个与 $x$ 直接相关的量，其下一次可能变化的位置分别为 $a2^\ell$ 和 $(\lfloor x/2^\ell\rfloor+1)2^\ell$。与 $s$ 相关的量则要等到 $\lfloor\sqrt x\rfloor$ 达到相应门槛，也就是等到 $x$ 达到门槛的平方。因此令
$$
r=\min\left\{
\begin{aligned}
&H+1,\\
&\left(\left\lfloor\frac{x}{2^\ell}\right\rfloor+1\right)2^\ell,\\
&a2^\ell,\\
&\left[\left(\left\lfloor\frac{s}{2^m}\right\rfloor+1\right)2^m\right]^2,\\
&(a2^m)^2
\end{aligned}
\right\}.
$$
四个量在 $[x,r-1]$ 上都保持不变。将这段记为一项，权重设为 $C(r-1)-C(x-1)$，然后直接跳到 $r$。这些门槛都严格大于当前 $x$，所以扫描必然前进，也不会漏掉变化位置。
接下来证明扫描出的区间数足够少。固定 $\ell\ge1$ 时，由位数公式可知 $a2^{\ell-1}\le x<a2^\ell$，因此 $\lfloor x/2^\ell\rfloor$ 只能在 $w$ 到 $2w$ 之间变化，共 $O(w)$ 种取值。当 $\ell=0$ 时，有 $0\le x<2w+1$，仍只有 $O(w)$ 种取值。总共有 $O(\log(H+1))$ 个位数层，所以 $(L_w(x),\lfloor x/2^{L_w(x)}\rfloor)$ 一共只变化 $O(w\log(H+1))$ 次。将自变量换成单调不减的 $A(x)$，变化次数不会增多。扫描时取这两组变化位置的并集，区间数仍为 $O(w\log(H+1))$。
得到各个区间后，还需要按 $(D_w,K_w)$ 选出最大的 $P$ 份。由于 $0\le D_w(x)\le F_w(H)=O(w\log(H+1))$，可以先按 $D_w$ 计数分桶，从大到小取。只有最后一个没能全部取走的收益桶需要比较 $K_w$；而 $K_w$ 在 $0$ 到 $O(\log(H+1))$ 之间，再开一个小桶即可。因此这一分支每次计算的总时间为 $O(w\log(H+1))$。
### 代价较大时，只重选高度分界附近的步骤
考虑 $\lceil\sqrt H\rceil\le w\le H$。此时 $A(x)\le w$，对 $A(x)$ 继续除以二不会严格改善附加代价，所以 $F_w(A(x))=A(x)$、$L_w(A(x))=0$。于是 $D_w(x)=F_w(x)-A(x)$，$K_w(x)=L_w(x)$。
我们先按起始高度从大到小，选取最大的 $P$ 份开方步骤，称为基准方案。它与 $w$ 无关，并且一定合法：一条开方链上，前一步的起始高度严格大于后一步，按高度选取不会越过未选的前缀。令 $c$ 为最后选到的高度；相同高度有多份时，可以只选其中一部分。实际执行这些步骤，得到一份固定的高度分布，便可用上一节的表在 $O(1)$ 时间内查询基准方案的附加代价与最少除法次数。
按高度选取本身不一定最优，但下面证明，错误只可能出现在分界 $c$ 附近。为了控制取整造成的波动，引入去掉除法取整的连续函数
$$
\Phi_w(t)=\min_{b\ge0}\left(\frac{t}{2^b}+wb\right),
\qquad
g_w(t)=\Phi_w(t)-\sqrt t.
$$
由于 $w,b$ 都是整数，对整数 $x$ 有 $F_w(x)=\lfloor\Phi_w(x)\rfloor$。因此 $D_w(x)-g_w(x)$ 等于两个取整误差之差，满足 $|D_w(x)-g_w(x)|<1$。
在 $1\le t\le H$ 上，$\Phi_w$ 是有限个相关直线段组成的连续函数。考察其中由某个 $b$ 取得最小值的一段。如果 $b=0$，则 $g'_w(t)=1-1/(2\sqrt t)\ge1/2\ge w/(2H)$。如果 $b\ge1$，由这一项不大于 $b-1$ 对应的项，得到
$$
\frac{t}{2^b}+wb
\le\frac{t}{2^{b-1}}+w(b-1)
\quad\Longrightarrow\quad
\frac{t}{2^b}\ge w.
$$
再利用 $w\ge\sqrt H\ge\sqrt t$，可得
$$
g'_w(t)
=\frac1{2^b}-\frac1{2\sqrt t}
\ge\frac wt-\frac1{2\sqrt t}
\ge\frac w{2t}
\ge\frac w{2H}.
$$
在各段上累加变化量，得到 $g_w(v)-g_w(u)\ge w(v-u)/(2H)$。所以当整数高度满足 $v-u>4H/w$ 时，有 $g_w(v)-g_w(u)>2$。两端的取整误差总共小于 $2$，从而必有 $D_w(v)>D_w(u)$。这就是只需处理分界附近的依据。
取 $R=\lfloor4H/w\rfloor+1$。若某一步的高度大于 $c+R$，它的收益严格大于所有高度不超过 $c$ 的步骤；而高度大于 $c$ 的步骤总数不足 $P$，所以这一步必定在最优选择中。类似地，若某一步的高度小于 $c-R$，高度至少为 $c$ 的不少于 $P$ 份步骤都严格优于它，所以它必定不会被选取。
因此，基准方案在窗口 $[\max(2,c-R),\min(H,c+R)]$ 之外的选择完全正确。先撤回基准方案在窗口内选中步骤的贡献，再将同样数量的名额按 $(D_w,K_w)$ 重新分配给窗口中的步骤即可。撤回时，将对应的 $D_w$ 加回附加代价，将 $K_w$ 加回除法次数；重新选取时做相反操作。这个计算与从所有开方步骤中全局选取最大的 $P$ 份完全一致，合法性继续由前文的链上单调性保证。
窗口长度是 $O(H/w)$，但分桶也必须控制在这个规模内。对整数高度，$F_w(x)$ 单调不减，且 $F_w(x+1)-F_w(x)\in\{0,1\}$：每个候选函数都有此性质，取最小值后仍然成立。同时 $A(x+1)-A(x)\in\{0,1\}$，所以这一分支中 $|D_w(x+1)-D_w(x)|\le1$。窗口内最大与最小收益之差不超过窗口长度，因此只需开从实际最小收益到实际最大收益的桶，而不是从 $0$ 或从 $1$ 开到最大收益。然后照样在最后一个收益桶中按 $K_w$ 选择。这样每次计算只需 $O(H/w+\log(H+1))$ 时间。
### 复杂度与完整实现
预处理高度频率、整数平方根、位数、开方步骤数、前缀和及两份固定分布的后缀表，总计 $O(n+H)$ 时间。小代价分支每次花费 $O(w\log(H+1))$，大代价分支每次花费 $O(H/w+\log(H+1))$。按 $\lceil\sqrt H\rceil$ 划分后，单次计算统一为 $O(\sqrt H\log(H+1))$；整数二分至多计算 $O(\log(H+1))$ 次，所以总时间为
$$
O\left(n+H+\sqrt H\log^2(H+1)\right)=O(n+H).
$$
最后一个等号使用了 $\log^2(H+1)=O(\sqrt H)$。这里采用通常的整数运算为常数时间的复杂度模型；保留等号左边的表达式，更便于看出算法各部分的代价。空间复杂度为 $O(H+1)$。这给出了关于 $n,H$ 的线性上界，并不等于证明了任何算法都需要 $\Omega(H)$ 时间。
代码将 $P$ 截断到有效开方步骤的总数。若 $P=0$，直接查询原始分布；若所有有效步骤都被选取，直接查询基准分布。全零输入也因此自然得到答案 $0$。其余情况在 $[1,\max(1,H)]$ 内二分，避免在大代价证明覆盖的范围外进行询问。高度和、总代价及平方门槛均使用 `long long`。输入时直接累计高度频率，不保留长为 $n$ 的输入数组。
下面是可独立编译的 GNU C++17 完整代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Result {
ll val, qmin;
};
// 一个固定高度分布的除法收益后缀表。
struct HalfTable {
ll sum = 0;
vector<ll> cnt, gain;
void build(const vector<int>& freq) {
int h = static_cast<int>(freq.size()) - 1;
vector<ll> c(freq.begin(), freq.end());
cnt.assign(h + 2, 0);
gain.assign(h + 2, 0);
sum = 0;
for (int x = h; x >= 1; --x) {
sum += 1LL * x * freq[x];
cnt[(x + 1) / 2] += c[x];
c[x / 2] += c[x];
}
for (int x = h; x >= 0; --x) {
gain[x] = gain[x + 1] + 1LL * x * cnt[x];
cnt[x] += cnt[x + 1];
}
}
Result query(int w) const {
int pos = min(w + 1, static_cast<int>(cnt.size()) - 1);
return {sum - gain[pos] + 1LL * w * cnt[pos], cnt[pos]};
}
};
struct Item {
int d, k, count;
};
struct OptimizedSolver {
int H, P, total, border = 0, threshold;
vector<int> rt, lg, cnt, pref, chosen;
HalfTable original, baseline;
OptimizedSolver(vector<int> freq, int p) : P(p) {
H = static_cast<int>(freq.size()) - 1;
rt.assign(H + 1, 0);
lg.assign(H + 1, 0);
for (int x = 1; x <= H; ++x) {
rt[x] = rt[x - 1];
if (1LL * (rt[x] + 1) * (rt[x] + 1) <= x) ++rt[x];
lg[x] = lg[x / 2] + 1;
}
threshold = rt[H] + (1LL * rt[H] * rt[H] < H);
original.build(freq);
cnt = freq;
for (int x = H; x >= 2; --x) cnt[rt[x]] += cnt[x];
pref.assign(H + 1, 0);
for (int x = 2; x <= H; ++x) pref[x] = pref[x - 1] + cnt[x];
total = H >= 2 ? pref[H] : 0;
P = min(P, total);
if (!P) return;
// 按步骤起始高度选最大的 P 份，并真正更新基准高度分布。
chosen.assign(H + 1, 0);
int need = P;
for (int x = H; x >= 2; --x) {
int take = min(need, cnt[x]);
chosen[x] = take;
if (take) border = x;
freq[x] -= take;
freq[rt[x]] += take;
need -= take;
}
baseline.build(freq);
}
// lg[t] 是 t 的二进制位数，lg[0]=0。
int divisions(int x, int w) const {
return lg[x / (2 * w + 1)];
}
int value(int x, int w, int b) const {
return (x >> b) + w * b;
}
// 按 (d,k) 降序选 need 份，返回总收益和节省的除法次数。
pair<ll, ll> select(const vector<Item>& items, int need) const {
if (!need) return {0, 0};
int low = H, high = 0;
for (const auto& t : items) {
low = min(low, t.d);
high = max(high, t.d);
}
vector<int> amount(high - low + 1, 0);
vector<ll> saved(high - low + 1, 0);
for (const auto& t : items) {
amount[t.d - low] += t.count;
saved[t.d - low] += 1LL * t.count * t.k;
}
ll gain_sum = 0, saved_sum = 0;
for (int d = high; d >= low; --d) {
if (need > amount[d - low]) {
gain_sum += 1LL * d * amount[d - low];
saved_sum += saved[d - low];
need -= amount[d - low];
continue;
}
gain_sum += 1LL * d * need;
vector<int> by_k(lg[H] + 1, 0);
for (const auto& t : items)
if (t.d == d) by_k[t.k] += t.count;
for (int k = lg[H]; k >= 0; --k) {
int take = min(need, by_k[k]);
saved_sum += 1LL * take * k;
need -= take;
}
return {gain_sum, saved_sum};
}
return {gain_sum, saved_sum};
}
Result calc(int w) const {
if (!P) return original.query(w);
if (P == total) return baseline.query(w);
vector<Item> items;
Result res;
int need;
if (w < threshold) {
res = original.query(w);
need = P;
for (int x = 2; x <= H;) {
int s = rt[x];
int l = divisions(x, w), m = divisions(s, w);
ll a = 2LL * w + 1;
ll next_s = (1LL * (s >> m) + 1) << m;
ll next_m = a << m;
ll r = min({
H + 1LL,
(1LL * (x >> l) + 1) << l,
a << l,
next_s * next_s,
next_m * next_m
});
int end = static_cast<int>(r);
int count = pref[end - 1] - pref[x - 1];
if (count) {
int d = value(x, w, l) - value(s, w, m);
items.push_back({d, l - m, count});
}
x = end;
}
} else {
res = baseline.query(w);
need = 0;
int radius = static_cast<int>(4LL * H / w + 1);
int left = max(2, border - radius);
int right = min(H, border + radius);
for (int x = left; x <= right; ++x) {
if (!cnt[x]) continue;
int k = divisions(x, w);
int d = value(x, w, k) - rt[x];
items.push_back({d, k, cnt[x]});
// 撤回窗口内基准方案的选择，再统一重新选取。
res.val += 1LL * chosen[x] * d;
res.qmin += 1LL * chosen[x] * k;
need += chosen[x];
}
}
auto [gain_sum, saved_sum] = select(items, need);
res.val -= gain_sum;
res.qmin -= saved_sum;
return res;
}
ll solve(int q) const {
Result first = calc(1);
if (q >= first.val) return 0;
int left = 1, right = max(1, H);
while (left < right) {
int mid = (left + right) / 2;
if (calc(mid).qmin <= q) right = mid;
else left = mid + 1;
}
return calc(left).val - 1LL * left * q;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, p, q, H = 0;
cin >> n >> p >> q;
vector<int> freq(1, 0);
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (x >= static_cast<int>(freq.size()))
freq.resize(max(x + 1, 2 * static_cast<int>(freq.size())), 0);
++freq[x];
H = max(H, x);
}
freq.resize(H + 1);
cout << OptimizedSolver(std::move(freq), p).solve(q) << '\n';
return 0;
}
```