（RMQ区间最值问题）给定序列a0, ... ,an-1，和m次询问，每次询问给定l，r，

求max{al, ... ,ar}。

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

m) ，步骤如下：

1、建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。

2、对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序

列），即求 Euler 序列上两点间一个新的 RMQ 问题。

3、注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。

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

4、设t为 Euler 序列长度。取 b = ?log2t / 2?。将序列每 b 个分为一大块，使用 ST表（倍

增表）处理大块间的 RMQ 问题,复杂度 O(t * logt / b)=O(n)。

5、（重点）对于一个块内的 RMQ 问题，也需要O(1)的算法。由于差分数组2b-1种，可以

预处理出所有情况下的最值位置，预处理复杂度 O(b2b)，不超过O(n)。

6、最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ问

题。

试补全程序。

①处应填（）