（RMQ区间最值问题）给定序列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 = ⌈log2t / 2⌉。将序列每 b 个分为一大块，使用 ST表（倍增表）处理大块间的 RMQ 问题,复杂度 O(t * logt / b)=O(n)。
	（重点）对于一个块内的 RMQ 问题，也需要O(1)的算法。由于差分数组2b-1种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2b)，不超过O(n)。
	最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ问题。
试补全程序。
![](https://ydschool-video.nosdn.127.net/16570794353401.jpg)![](https://ydschool-video.nosdn.127.net/16570794459552.jpg)![](https://ydschool-video.nosdn.127.net/16570794521783.jpg)![](https://ydschool-video.nosdn.127.net/16570794599704.jpg)
![](https://ydschool-video.nosdn.127.net/16570794652555.jpg)
①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）
⑥处应填（）
1. A.p->son[0] = S[top--]  B.p->son[1] = S[top--]  C.S[top--]->son[0] = p  D.S[top--]->son[1] = p
2. A.p->son[0] = S[top]   B.p->son[1] = S[top]   C.S[top]->son[0] = p    D.S[top]->son[1] = p
3. A.x->dep < y->dep     B.x < y             C.x->dep > y->dep      D.x->val < y->val
4. A.A[i * b + j - 1] == A[i * b + j]->son[0]     B.A[i * b + j]->val < A[i * b + j - 1]->val     C.A[i * b + j] == A[i * b + j - 1]->son[1]        D.A[i * b + j]->dep < A[i * b + j - 1]->dep
5. A.v += (S >> i & 1) ? -1 : 1           B.v += (S >> i & 1) ? 1 : -1        
  C.tv += (S >> (i - 1) & 1) ? 1 : -1    D.v += (S >> (i - 1) & 1) ? -1 : 1
6. A.(Dif[p] >> (r - p * b)) & ((1 << (r - l)) - 1)         B.Dif[p]  
   C.(Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1) 
   D.(Dif[p] >> ((p + 1) * b - r)) & ((1 << (r - l + 1)) - 1)


有道小图灵信息学

2021CSP提高级第一轮认证

有道小图灵 信息学

2021CSP提高级第一轮认证

有道小图灵信息学