自动搬运

查看原文

来自洛谷，原作者为

	what_else ？？？

搬运于2025-08-24 22:50:19，当前版本为作者最后更新于2023-09-11 18:24:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

Hard Version

感谢 @syksykCCC 对 Easy Ver 的看法与见解，于是有了这道 Hard Ver。

%%% %%%

接下来考虑，在只能篡改一道题难度的情况下，怎样求方案数。

如果用 $t$ 表示篡改后的难度值，用 $f(t)$ 表示篡改难度值为 $t$ 的总可做性，那么 $f(t)$ 单调递增。

但 $f(t)$ 是不是严格单调递增的呢？其实，对于当 $t$ 小于前 $1 \sim m-1$ 个数中 $k$ 个较大者的最小值，$f(t)$ 均相等，即篡改没有影响。

但是大于时，这就严格单调递增了。

那么解法好想：提前处理以上的非单调情况，然后二分 $a_m$ 的上下界，$a_m$ 的单调取值显然就是 $[l,r]$ 的取值。

总时间复杂度为 $O(n \log n \log V)$。

感谢