自动搬运

查看原文

来自洛谷，原作者为

	Cocoly1990 成事不说 遂事不谏 既往不咎

搬运于2025-08-24 22:55:16，当前版本为作者最后更新于2024-05-30 21:06:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

官方题解

考虑从序列从前向后确定每个值，对 $[1,i-1]$ 二分 $rank$ 可以得到 $i$，代价为 $\sum \frac{1}{i}\log i$，代价大约 $34$。

考虑值域从大到小确定每个值，当求出前 $x$ 大时，很容易设计一个比较器，使得在一次询问内求出区间 $[l,r]$ 内是否包含第 $x+1$ 大。

一个有趣的发现：将序列分两份，我们可以用一次询问来确定 $x$ 在序列的左侧还是右侧，之后每次二分的时候我们都保证了询问区间长度 $>\frac{n}{2}$。

这样可以容易做到 $n\times \frac{2}{n}\times (\log n+1)$。大约是 $22$ 次。

考虑结合两个做法，把序列分两段，用 $1$ 的代价确定两块的构成，然后运用做法一，可以做到 $\sum \frac{1}{\max\{i,n-i\}}\log i$，大约是 $14$ 次。

还能不能再给力一点！注意到 $\log i$ 实现的精细一点可以做到 $\log \min\{i,n-i+1\}$，这样理论分析就可以做到 $<11.8$ 次。

经过构造可以把标算卡到基本满。