CF1466I better solution

· · 题解

下文中以 m 代指 b。

我们先尝试把 a_i 范围（记作 [L_i,R_i]）的大小从 2^m 缩小到 2^{m-i} 以下，使范围变为阶梯状。假设我们现在已经确定完前 i-1 项，正尝试判断第 i 项。如果 a_i < 2^{m-i}，则继续处理下一位，否则从第 i-1 项开始往左枚举，设已经枚举到了第 j 项，如果 a_i \geq 2^{m-j}，则我们可以直接抛弃 a_j，因为 a_j < 2^{m-j} \leq a_i，a_j 已无法成为数列中的最大值。否则就此停止。除去抛弃的项，我们组成一个新的数列，可以发现 每一个数的范围都符合了我们的要求。

然后我们将每个数的范围变成这样的阶梯状后，我们再尝试把它变回 a_i<2^k(k<m) 的平地状。维护双指针 l,r。如果 a_l > R_r，我们可以直接抛弃 a_r，否则，a_l 的最大值最大只能是 a_r 的最大值，我们对 a_l 的范围进行修改。手玩一下，发现最终最大值 <2^k 的都被丢弃，剩下的 a_i 范围大小均 <2^k。

通过以上两个操作，我们将原问题转换为了一个规模更小的子问题，可以递归求解。考虑分析操作次数，设最后剩下了 x 个数，每个数的范围大小都是 2^{m-x}，在变成阶梯状时需遍历 1 到 n ，共 n 次询问（下文称之为 1 类询问）；在上文的双指针过程中产生的询问（下文称之为 2 类询问）与平地状变阶梯状时删除某些元素产生的询问（下文称之为 3 类询问），考虑 n 个元素中进行过 2 类询问的元素会被删除而无法进行 3 类询问，因此 2,3 类询问的次数和不超过 n ；在平地状变成阶梯状的过程中，当 a_i\geq 2^{m-i} 时，会产生一次询问而不删除任何元素（下文称之为 4 类询问），这种询问最多有 n 次，因此有 \text{T}(m,n)=\max_{x=1}^{\min(n-1,m)}\text{T}(m-x,x)+3n，用程序计算发现总操作次数不超过 3(n+m)，是原题给出的次数上限。

考虑加入一个简单剪枝：当此时已确定的数列最大值的下限（\max_{i=1}^nL_i)不低于某个数的上限，则删除这个数。考虑分析次数：设分别进行了 y_1,y_2,y_3,y_4 次 1,2,3,4 类询问。发现如果对第 i 个数进行了一次 4 类询问。则它的上界与其左侧相邻数的上界是相同的。如果该数经过一次 3 类询问而被删除，则会顺带删除其左边相邻的数。均摊下来，相当于其并未执行 4 类询问。

设阶梯状变为平地状后从 x_1 个数变为 x 个数。则 y_2 次 2 类询问中共删除 x_1-x 个数，留下 x 个数。如果有进行过 4 类询问的数在这个过程中被删除，仍然可以通过上文一样的方法将这一次 4 类询问均摊进入 2 类讯问中。则最终，没被均摊掉的 4 类询问至多只有 x 次。这样计算，1 类询问仍然有 n 个，2,3 类询问的和依然是至多 n 次，但真正贡献次数的 4 类询问最多只有 x 个，有 \text{T}(m,n)=\max_{x=1}^{\min(n-1,m)}\text{T}(m-x,x)+2n+x,用程序计算发现总操作次数不超过 2n+3m。

提交记录：https://codeforces.com/contest/1466/submission/273256175

我个人认为本题的询问次数仍有一定的改进空间，毕竟 x 只是 4 类操作的一个上界。欢迎大家继续与我探讨本题的做法。

这个做法是我在两年前的机房，班主任喊我去自习，我不希望自习而在本子上抄下了这一道题带回去做时想出来的。当时我只是粗略估计到了 3(n+m) 的次数上限。昨天我将这个题搬到了模拟赛，在睡觉时复习着次数上线的证明时发现这个做法实际上是 2n+3m 次的。

在功利的环境下，我可能早已被抹平了棱角，对未来充满了麻木。可现在，我仿佛又找回到最初最纯粹的对追求未知的热爱。