六、完善程序-2

（ RMQ 区间最值问题） 给定序列 a₀,⋯,a_n−1, m 次询问，每次询问给定 l,r，求 max⁡{a_l, …,a_r}。

为了解决该问题，有一个算法叫 the Method of Four Russians ，其时间复杂度为 O(n+m) ，步骤如下：

• 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。
• 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。
• 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。

下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列：

• 设 t为 Euler 序列长度。取 b=⌈\(\frac{log_{2}t}{2}\)⌉将序列每 b个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 O(\(\frac{t}{b})log⁡t)=O(n)。
• （重点） 对于一个块内的 RMQ 问题，也需要 O(1)的算法。由于差分数组 2^b−1 种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2^b)，不超过 O(n)。
• 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。

试补全程序。