接我上一个问题“范围最小查询方法(从树到受限RMQ) ”(建议阅读)
同样,在 TopCoder 上的本教程中,我到处都有一些问题,我希望有人能解决它们。
因此,我将 RMQ(最小范围查询)问题转换为 LCA(最低公共祖先)问题,然后将其转换回来,我可以得到一个简化的数组。(两种变换都可以在教程中找到,简化的数组是“从LCA到RMQ”中讨论的数组L)
无论如何,我可以使用 Euler Tour 得到那个数组,这是所有计算的核心部分。
首先,我需要通过使整个数组仅包含 1 和 -1 来使其更简单,所以这就是我所做的Ls[i] = L[i] - L[i-1]
:
第二步实际上是分区,这很简单,但是第三步让我感到困惑。
令 A'[i] 为 A 中第 i 个块的最小值,B[i] 为该最小值在 A 中的位置。
A指的是这句话中的L数组,所以最小值总是1或-1,并且会有多个1和-1。这让我很困惑,因为我认为这不会让计算变得更容易。
第四步,
现在,我们使用第 1 节中描述的 ST 算法对 A' 进行预处理。这将花费 O(N/l * log(N/l)) = O(N) 时间和空间。
如果 A' 只保留 1 和 -1 的记录,那么在上面做任何事情似乎都没用。
最后一步,
为了索引表 P,预处理 A 中每个块的类型并将其存储在数组 T[1, N/l] 中。块类型是通过将 -1 替换为 0 并将 +1 替换为 1 获得的二进制数。
这是什么意思?计算每种组合?比如000
———— 001
……?
它看起来像多个问题,但我希望有人可以引导我完成最后的这些步骤。谢谢!