CSP-S 提高级 · CSP 2021 提高级第一轮 第 20 题

(2) （ RMQ 区间最值问题） 给定序列 $a_0,\cdots,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 问题。

• 注意新的问题为 $\pm1$ RMQ，即相邻两点的深度差一定为 $1$。

下面解决这个 $\pm1$ RMQ 问题，“序列”指 Euler 序列：

• 设 $t$ 为 Euler 序列长度。取 $b=\lceil \frac{\log_2 t}{2} \rceil$ 将序列每 $b$ 个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 $O(\frac{t}{b}\log t)=O(n)$。

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

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

试补全程序。

   

38. ①处应填（ ） A. p->son[0] = S[top--] B. `p->

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是 Four Russians 算法把 RMQ 转成±1RMQ 的完整流程。拿到题先想：建树用单调栈维护右链，Euler 序的深度差恒为±1 才能状态压缩。从①的左子树弹出开始，一步步连右链、比深度、判差分、还原编码，最后提取块内片段。

最容易在①②搞反父子方向：单调栈里弹出的栈顶是新节点的左孩子，栈顶的前驱的右孩子是新节点，别把箭头指反。③④⑤涉及深度比较和差分还原，很多人记反了 0/1 对应的增减方向，或者把相邻元素顺序搞反，导致查出来的编码段错位。⑥提取片段时偏移量算错是高频坑，记住是从当前块起点 r-p*b 开始取长度 r-l 的段，别用 l-p*b 或总长度减一。

这道题考查 Four Russians 算法，核心是把区间最值问题通过笛卡尔树、Euler 序转化为±1RMQ，再用分块和状态压缩做到 O(1) 查询。

先理清概念：RMQ 是求区间最大/最小值；笛卡尔树满足中序遍历为原序列且为大根堆；Euler 序记录 DFS 经过每个点的时刻，相邻点深度差必为±1，因此可以用 2 比特编码（0 表示+1，1 表示-1）；Four Russians 把序列每 b 个分一大块，块间用 ST 表，块内预处理所有 2^{2b} 种差分情况。

命题人爱挖的坑：①②是建树时的父子链接方向，③④⑤是±1RMQ 的编码判读，⑥是提取片段时的偏移量。

38 题：单调栈维护右链，新节点 p 的左子树由栈顶弹出得到，即 p->son[0] = S[top--]，选 A。 39 题：p 的前驱（当前栈顶）的右子树应指向 p，即 S[top]->son[1] = p，选 D。 40 题：LCA 深度更小，比较 x->dep < y->dep，选 A。 41 题：差分编码中 0 表示深度增加，即当前点深度大于前一个，故 A[i*b+j]->dep < A[i*b+j-1]->dep 为假，选 D。 42 题：还原时 S 的第 i-1 位为 1 表示深度减 1，为 0 表示加 1，即 v += (S>>(i-1)&1)?1:-1，选 C。 43 题：从块 p 的起点 r-p*b 开始取长度 r-l 的片段，即 (Dif[p]>>(r-p*b))&((1<<(r-l))-1)，选 A。

考频与趋势：数据结构在题库共考 5 题，2021 年 CSP 提高级考过 2 题；树形结构 26 题，2021 年 2 题；二叉树基础 220 题，2021 年 4 题；二叉树遍历 201 题，2021 年 2 题；LCA 仅 2 题，2021 年 1 题。可见±1RMQ 是近年 CSP 提高级的冷门但高频考点，2023-2026 年树形结构考题明显增多（2026 年达 8 题），未来仍可能以“分块+状态压缩”形式出现。

暂无足够依据预测具体题型变化，但建议重点掌握单调栈建树、Euler 序深度性质、差分编码还原与片段提取。