给定序列 a0,⋯,an−1,m 次询问，每次询问给定 l,r, 求 max{al, ...,ar}。
为了解决该问题，有一个算法叫 the Method of Four Russians ，其时间复杂度为 O(n+m) ，步骤如下：
建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。
对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。
注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。
下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列：
设 t 为 Euler 序列长度。取 b=⌈log2t2⌉将序列每 b 个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 OO(btlogt)=O(n)。
（重点） 对于一个块内的 RMQ 问题，也需要 O(1) 的算法。由于差分数组 2b−12b−1 种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2b)，不超过O(n)。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。
00