魔法题。

题目要求我们求 $n$ 个长度为 $2^m-1$ 的递增序列的第 $k$ 小元素。

算法 1

暴力求出来一整个数组所有元素并且排序，询问用量 $O(n2^{m})$，期望得分 $10$ 分。

算法 2

二分答案，再在每一行二分边界，询问用量 $O(nm\log\max)$，期望得分 $29$ 到 $41$ 分。

算法 3

长度 $2^m-1$ 提醒到一个类似于线段树的做法。

我们维护一个 当前精度 $d$，初始为 $2^{m-1}$，和 当前长度 $t$，初始为 $1$。

定义当前 对应序列 为每一个序列每 $d$ 元素提取出最后一个形成的 $n$ 个序列。 定义当前 答案估计 为对应序列的全局 $\lfloor k\frac{t}{2^m-1}\rfloor$ 小。
定义当前 划分 为对应序列里每一个序列的一个前缀，代表小于答案估计的元素集合。

初始时候可以暴力提取出来每一个序列的第 $2^{m-1}$ 元素计算答案估计。
每一轮，会进行如下操作：

1. 将 $d$ 除以 $2$，将 $t$ 设为 $2t+1$。
2. 如果 $d=0$，那么上一轮已经找到答案了，停止。
3. 先计算这轮的对应序列的划分的一个估计：不用这一轮的答案估计，而用上一轮的答案估计，构造出来这一轮的划分估计。
4. 从上一轮的划分可以得到每一个序列有一个后缀必须不在划分估计里，有一个前缀必须在划分估计里。
5. 上一轮的划分的结尾元素紧靠的下一个元素为唯一没有固定位置在划分估计里，我们需要提取它的值并且将它与上一轮的答案估计比较，判断是否加入前缀。
6. 现在前缀大小会产生偏差。我们想让前缀包含恰好 $\lfloor k\frac{t}{2^m-1}\rfloor$ 元素，但是可能比较的时候导致前缀变更小或更大。定当前所有前缀大小之和为 $x$。
7. 如果 $x>\lfloor k\frac{t}{2^m-1}\rfloor$，则把前缀外的最小 $x-\lfloor k\frac{t}{2^m-1}\rfloor$ 元素移动进前缀。
8. 否则把前缀里的最大 $\lfloor k\frac{t}{2^m-1}\rfloor-x$ 值移动出前缀。
9. 这些步骤直接用 $priority\_queue$ 即可；我们可以重新定义一个类型的 operator< 来调用交互库获取值。
10. 更新答案估计。

最终答案必定为答案估计，由于最终 $t=2^m-1$ 所以最后必须答案估计是第 $k$ 小。
接下来证明调用次数的复杂度；我们逐轮考虑。

第 5 步会贡献恰好 $n$ 个访问。
第 10 步会贡献恰好 $n$ 个访问。
剩下唯一可能贡献访问的地方是 7 和 8。$|\lfloor k\frac{t}{2^m-1}\rfloor-x|$ 是 $O(n)$。我们分别证明（1） $|\lfloor k\frac{t}{2^m-1}\rfloor-2\lfloor k\frac{\frac{t-1}{2}}{2^m-1}\rfloor|=O(n)$ 并且 （2） $|2\lfloor k\frac{\frac{t-1}{2}}{2^m-1}\rfloor-x|=O(n)$。

1. $k$ 最大这个表达式会最大化；$|\lfloor n(2^m-1)\frac{t}{2^m-1}\rfloor-2\lfloor n(2^m-1)\frac{\frac{t-1}{2}}{2^m-1}\rfloor|=|\lfloor nt\rfloor-2\lfloor n\frac{t-1}{2}\rfloor|$ 然后 $=\lfloor nt\rfloor-2\lfloor n\frac{t-1}{2}\rfloor\le nt-n(t-1)+1=O(n)$
2. $2\lfloor k\frac{\frac{t-1}{2}}{2^m-1}\rfloor$ 就是在第 5 步前的总共前缀大小，仅添加 $O(n)$ 元素。

于是理论上每一轮需要 $6n$ 访问；但是加一个缓存根本不可能卡到这样。
询问用量 $O(nm)$，期望得分 $100$ 分。