#创作计划# 猎奇

复仇者_帅童

2025-09-03 06:58:40

发布于：广东

18阅读

0回复

0点赞

在“忠诚”这题中，我使用了乱搞解法，因为数据水通过了。

做法如下：

将 $A$ 数组从大到小排序，并且记录每个数原来的下标。
查询时，将 $A$ 数组从头到尾遍历一遍，找到第一个原来的下标在询问区间内的数，并输出它。

这么猎奇的做法为什么能过呢？原来它在随机数据（ $A_i$ ，查询区间的左、右端点均随机生成）下，时间复杂度期望 $O(q\log n)$ ！接下来，我要证明这个结论：

由于随机生成，所以排序后原来的下标也是随机的。这就相当于在数组中随机撒点，看看哪个点最先落在区间上。显然，如果长度为 $l$ ，每次撒点撒中的概率为 $\frac{l}{n}$ ，而有点撒中的期望撒点次数为 $\frac{n}{l}$ 。

那 $l$ 为多少呢？显然它由区间的左右端点决定。注意到区间左右端点是随机的，所以 $l=1$ 的概率约为 $\frac{n}{n^2}$ ， $l=2$ 的概率为 $2\times \frac{n-1}{n^2}$ ， $l=3$ 的概率为 $2\times \frac{n-3}{n^2}$ ，......， $l=n$ 的概率为 $2\times \frac{1}{n^2}$ 。

所以，整体的期望如下：

$\frac{n}{n^2}\times \frac{n}{1}+ 2(\frac{n-1}{n^2}\times \frac{n}{2}+\frac{n-2}{n^2}\times \frac{n}{3}+...+\frac{1}{n^2}\times \frac{n}{n})\\\space\\ \lt2(\frac{n+1}{n}+\frac{n}{2n}+\frac{n-1}{3n}+...+\frac{2}{n^2})\\\space\\ \lt 2(\frac{n+1}{n}+\frac{n+1}{2n}+\frac{n+1}{3n}+...+\frac{n+1}{n^2})\\\space\\ =2(\frac{n+1}{n})(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})\\\space\\ \lt 2(\frac{n+1}{n})(\frac{1}{1}+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+...+\frac{1}{2^{\lfloor\log_2 n\rfloor}}+\frac{1}{2^{\lfloor\log_2 n\rfloor}}+...+\frac{1}{2^{\lfloor\log_2 n\rfloor}})\\\space\\ =2(\frac{n+1}{n})(\lfloor \log_2 n\rfloor+1)\\\space\\ =O(\log n)$