在“忠诚”这题中，我使用了乱搞解法，因为数据水通过了。
做法如下：
* 将 AAA 数组从大到小排序，并且记录每个数原来的下标。
* 查询时，将 AAA 数组从头到尾遍历一遍，找到第一个原来的下标在询问区间内的数，并输出它。
这么猎奇的做法为什么能过呢？原来它在随机数据（AiA_iAi ，查询区间的左、右端点均随机生成）下，时间复杂度期望 O(qlogn)O(q\log n)O(qlogn)！接下来，我要证明这个结论：
由于随机生成，所以排序后原来的下标也是随机的。这就相当于在数组中随机撒点，看看哪个点最先落在区间上。显然，如果长度为 lll，每次撒点撒中的概率为 ln\frac{l}{n}nl ，而有点撒中的期望撒点次数为 nl\frac{n}{l}ln 。
那 lll 为多少呢？显然它由区间的左右端点决定。注意到区间左右端点是随机的，所以 l=1l=1l=1 的概率约为 nn2\frac{n}{n^2}n2n ，l=2l=2l=2 的概率为 2×n−1n22\times \frac{n-1}{n^2}2×n2n−1 ，l=3l=3l=3 的概率为 2×n−3n22\times \frac{n-3}{n^2}2×n2n−3 ，......，l=nl=nl=n 的概率为 2×1n22\times \frac{1}{n^2}2×n21 。
所以，整体的期望如下：
nn2×n1+2(n−1n2×n2+n−2n2×n3+...+1n2×nn) <2(nn+n−12n+n−23n+...+1n2) <2(nn+n2n+n3n+...+nn2) =2(11+12+13+...+1n) <2(11+12+12+14+14+14+14+...+12⌊log2n⌋+12⌊log2n⌋+...+12⌊log2n⌋) =2(⌊log2n⌋+1) =O(logn)\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}{n}+\frac{n-1}{2n}+\frac{n-2}{3n}+...+\frac{1}{n^2})\\\space\\ \lt 2(\frac{n}{n}+\frac{n}{2n}+\frac{n}{3n}+...+\frac{n}{n^2})\\\space\\ =2(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})\\\space\\ \lt
2(\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(\lfloor \log_2 n\rfloor+1)\\\space\\ =O(\log n) n2n ×1n +2(n2n−1 ×2n +n2n−2 ×3n
+...+n21 ×nn ) <2(nn +2nn−1 +3nn−2 +...+n21 ) <2(nn +2nn +3nn +...+n2n ) =2(11 +21 +31 +...+n1 ) <2(11 +21 +21 +41 +41 +41 +41 +...+2⌊log2 n⌋1 +2⌊log2 n⌋1 +...+2⌊log2 n⌋1 ) =2(⌊log2 n⌋+1) =O(logn)
所以时间复杂度为 O(qlogn)O(q\log n)O(qlogn)。
hack 这个算法的做法也挺简单的，一种做法如下：
将第 iii 次询问的区间设置成 [i,i][i,i][i,i] 即可。
显然无论 AAA 数组长什么样，这些查询会让该算法分别撒点 111 次，222 次，333 次，......，nnn 次，时间复杂度退化为 O(qn)O(qn)O(qn)。
