A61578 | RMQ区间最值问题）给定序列a0, … ,an-1，和m次询问，每次询问给定l,r，求max {al, … ,ar}为了解决该问题，有一个算法叫theMethodofFourRussians，其时间复杂度为O(n+m)，步骤如下：·建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。·对于 LCA问题，可以考虑其 Euler序（即按照 DFS过程，经过所有点，环…

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

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

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

·对于 LCA问题，可以考虑其 Euler序（即按照 DFS过程，经过所有点，环游回根的序列），即求 Euler序列上两点间一个新的 RMQ问题。

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

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

·设t为 Euler序列长度。取b=[]。将序列每b个分为一大块， 使用 ST表（倍增表）处理大块间的 RMQ问题，复杂度O(logt)=O(n)。

·（重点）对于一个块内的 RMQ问题，也需要O(1) 的算法。由于差分数组 2^b-1种，可以预处理出所有情况下的最值位置，预处理复杂度O(b2^b)，不超过O(n

)。

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

试补全程序。

 #include <iostream>
 #include <cmath>
 
 using namespace std;
 
 const int MAXN = 100000, MAXT = MAXN << 1;
 const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;
 
 struct node {
     int val;
     intdep, dfn, end;
     node *son[2]; // son[0], son[1] 分别表示左右儿子
 } T[MAXN];
 
 int n, t, b, c, Log2[MAXC + 1];
 int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
 node *root, *A[MAXT], *Min[MAXL][MAXC];
 
 void build() { // 建立 Cartesian 树
     static node *S[MAXN + 1];
     int top = 0;
     for (int i = 0; i < n; i++) {
         node *p = &T[i];
         while(top && S[top]->val < p->val)
             ①;
         if (top)
             ②;
         S[++top] = p;
     }
     root = S[1];
 }
 
 void DFS(node *p) { // 构建 Euler 序列
     A[p->dfn = t++] = p;
     for (int i = 0; i < 2; i++)
         if (p->son[i]) {
             p->son[i]->dep = p->dep + 1;
             DFS(p->son[i]);
             A[t++] = p; 
         } 
     p->end = t   1; 
 }