代码解析：完善程序-2

信息学奥赛历年真题 2021年NOIP提高组真题代码解析：完善程序-2

代码逻辑分析

这份代码实现的是 在线 RMQ（区间最小值查询）/ LCA（最近公共祖先）算法，具体逻辑如下：

数据结构
- node：表示树的节点，包含值 val、深度 dep、DFS 序编号 dfn、子树范围 end 以及左右儿子指针。
- A[]：Euler 序列数组，用于存储 DFS 遍历过程中访问的节点。
- Min[][]：ST 表（稀疏表），用于块间 RMQ 查询。
- Dif[]、Pos[]：用于块内 RMQ 的预处理。
build()：构建 Cartesian 树
- 根据输入序列的值构造一棵 Cartesian 树。
- 这里的逻辑利用了单调栈，保持栈内元素递增，构造出一个堆性质的树。
DFS()：建立 Euler 序列
- 从根开始深度优先遍历，将节点加入 Euler 序列 A[]。
- 每次回溯时再记录一次当前节点，用于区间 RMQ。
min(x, y)
- 比较两个节点，返回深度更小的那个（即 RMQ 的本质：谁在 Euler 序列中更浅）。
- 这里的 ③ 就是比较 x->dep < y->dep。
ST_init()：构建 ST 表
- 将 Euler 序列分块，每块大小 b ≈ log2(t)/2。
- 每块取最小值作为基准，构造稀疏表 Min[][]，用于块间 RMQ。
small_init()：块内 RMQ 预处理
- 通过位运算枚举块内所有可能的区间，记录每个状态下的最小值位置。
- Dif[] 存储块内相邻元素比较结果的差分。
- Pos[] 存储状态对应的最小值位置。
ST_query(l, r)
- 用稀疏表在 O(1) 时间内返回两个块之间的最小值。
small_query(l, r)
- 在同一块内部时，使用 Pos[] 的预处理结果快速求区间最小值。
query(l, r)
- 先判断是否在同一块：
  - 同一块 → small_query
  - 跨块 → 左边界块 + 右边界块用 small_query，中间完整块用 ST_query，再取最小值。
- 这相当于 “分块 RMQ + ST 表” 的结合。
main() 主函数
- 输入 n 个值，构建 Cartesian 树。
- DFS 得到 Euler 序列。
- 初始化 ST 表和块内 RMQ。
- 每次查询 (l, r) → 转换为 Euler 序区间 (T[l].dfn, T[r].dfn)，输出最小值节点的 val。
- 实际上就是求两点的 最近公共祖先 (LCA)。

代码详解：

#include <iostream>
#include <cmath>
using namespace std;

/*
整体思路（LCA/RMQ 一体化）：
1) 由原数组值构造 Cartesian 树（保持中序为原序、堆序为值最大堆）。
2) 对树做 Euler Tour（每到一个点入栈一次，回溯再入一次），得到序列 A[0..t-1]。
   —— LCA(u,v) 即 Euler 序中区间 [dfn[u], dfn[v]] 的“最小深度”节点。
3) 对 Euler 序做“分块 + 稀疏表（ST）”：
   - 块内（同一块）用位运算编码相邻深度上/下走向，预处理出所有子区间的最小位置（Pos）。
   - 块间（整块）用 ST 表做 RMQ。
查询：
  若 l、r 在同一块 → small_query
  若跨块 → 左残块 + 右残块 small_query，中间整块 ST_query，再取深度更小者
*/

const int MAXN = 100000;          // 原数组最大长度
const int MAXT = MAXN << 1;       // Euler 序长度上界（每个点最多两次进入）
const int MAXL = 18;              // ST 表层数上界（log2(MAXC) < 18）
const int MAXB = 9;               // 每块最多 2^(MAXB-1) 个状态（b<=9 足够）
const int MAXC = MAXT / MAXB;     // 最多块数上界

struct node {
    int val;                      // 原数组值 / Cartesian 树结点权值
    int dep, dfn, end;            // 深度、在 Euler 序中的首次出现位置 dfn、子树区间右端 end
    node *son[2];                 // 左右儿子指针：son[0]=left, son[1]=right
} T[MAXN];

int n, t;                         // n=节点数；t=Euler 序长度
int b, c;                         // b=块大小；c=块数（t/b）
int Log2[MAXC + 1];               // 预处理 log2
int Pos[(1 << (MAXB - 1)) + 5];   // 对任意“相邻差分位串”S，最小前缀位置（块内 RMQ 用）
int Dif[MAXC + 1];                // 每块相邻差分位串：第 j 位为 1 表示 depth[j] < depth[j-1]
node *root;                       // Cartesian 树根
node *A[MAXT];                    // Euler 序（指针数组，指向 node）
node *Min[MAXL][MAXC];            // ST 表（以块为单位，存每块的最小深度结点）

// 以原数组值构造 Cartesian 树：中序为原序，堆序为“值最大堆”
void build() {
    static node *S[MAXN + 1];     // 单调栈：严格递增（栈底小、栈顶大）
    int top = 0;
    for (int i = 0; i < n; i++) {
        node *p = &T[i];
        // 把比当前 p 值小的全部弹出，并接到 p 的左儿子链上（保持“值最大堆”）
        while (top && S[top]->val < p->val)
            p->son[0] = S[top--];                 // ① 左儿子链接为出栈元素
        if (top)
            S[top]->son[1] = p;                   // ② 栈顶作为 p 的父，p 是其右儿子
        S[++top] = p;                             // p 入栈
    }
    root = S[1];                                  // 栈底即整棵 Cartesian 树的根
}

// 对 Cartesian 树做 Euler Tour，A[] 记录访问序列
void DFS(node *p) {
    A[p->dfn = t++] = p;                          // 进入 p，入序列
    for (int i = 0; i < 2; i++)
        if (p->son[i]) {
            p->son[i]->dep = p->dep + 1;          // 子节点深度 = 父深度 + 1
            DFS(p->son[i]);                       // 递归
            A[t++] = p;                           // 回溯，再次把 p 放入 Euler 序
        }
    p->end = t - 1;                               // 子树在 Euler 序的闭区间 [dfn, end]
}

// 比较两个结点的深度，返回更浅者（RMQ 的本质）
node *min(node *x, node *y) {
    return (x->dep < y->dep) ? x : y;             // ③
}

// 构造“块间 RMQ”的 ST 表；并初始化每块的“块内最小”
void ST_init() {
    // 选块大小 b：这里用 ceil(log2(t)/2)，经验上块大小 ≈ logn/2
    b = (int)(ceil(log2(t) / 2));
    c = t / b;                                    // 完整块个数（剩余不足一块的忽略 ST，只走 small）
    Log2[1] = 0;
    for (int i = 2; i <= c; i++)
        Log2[i] = Log2[i >> 1] + 1;

    // 每块的“块内最小”结点（以深度比较）
    for (int i = 0; i < c; i++) {
        Min[0][i] = A[i * b];
        for (int j = 1; j < b; j++)
            Min[0][i] = min(Min[0][i], A[i * b + j]);
    }
    // ST 表：Min[k][j] 表示长度为 2^k 块，从 j 开始的块区间的最小
    for (int i = 1, l = 2; l <= c; i++, l <<= 1)
        for (int j = 0; j + l <= c; j++)
            Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
}

// 块内预处理：把“相邻深度比较”压成位串，再为所有位串状态预出“前缀最小位置”
void small_init() {
    // 生成每块的相邻差分位串 Dif[i]
    // 第 (j-1) 位 = 1 表示 depth[j] < depth[j-1]（下坡），否则为 0（上坡/持平）
    for (int i = 0; i <= c; i++)
        for (int j = 1; j < b && i * b + j < t; j++)
            if (A[i * b + j]->dep < A[i * b + j - 1]->dep)  // ④
                Dif[i] |= 1 << (j - 1);

    // 对每一个可能的状态 S（长度 b-1 的位串），计算其“前缀和最小值首次出现位置”
    // 规则：位 1 视为 -1，位 0 视为 +1；v 为前缀和；记录 v 的最小值所在 i（1..b-1）
    for (int S = 0; S < (1 << (b - 1)); S++) {
        int mx = 0, v = 0;                        // mx 记录“最小前缀和”；v 为当前前缀和
        for (int i = 1; i < b; i++) {
            v += (((S >> (i - 1)) & 1) ? -1 : 1); // ⑤ 1:-1, 0:+1
            if (v < mx) {
                mx = v;
                Pos[S] = i;                       // 位置 i 即子区间内最小深度的“右端位置”
            }
        }
    }
}

// ST 表查询：在块级区间 [l, r]（闭区间，单位=块）中找最小深度结点
node *ST_query(int l, int r) {
    int g = Log2[r - l + 1];
    return min(Min[g][l], Min[g][r - (1 << g) + 1]);
}

// 同块内的 RMQ 查询：利用 Dif[p] 的位串子段快速确定最小位置
node *small_query(int l, int r) {
    int p = l / b;                                 // 所在块编号
    // 取该块的位串中，对应 [l, r] 子段的状态：
    //   向右移去掉左边 l 之前的位，再截取长度 (r-l) 的低位。
    int S = (Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1);  // ⑥
    // Pos[S] 为从 l 开始的偏移（1..b-1），l + Pos[S] 即最小深度元素下标
    return A[l + Pos[S]];
}

// 对 Euler 序区间 [l, r] 做 RMQ：若同块走 small，否则两端残块 small + 中间整块 ST
node *query(int l, int r) {
    if (l > r) return query(r, l);
    int pl = l / b, pr = r / b;
    if (pl == pr) {
        return small_query(l, r);
    } else {
        // 左残块 [l, pl*b+b-1] 与 右残块 [pr*b, r]
        node *s = min(small_query(l, pl * b + b - 1),
                      small_query(pr * b, r));
        // 中间完整块 [pl+1, pr-1] 用 ST 表
        if (pl + 1 <= pr - 1)
            s = min(s, ST_query(pl + 1, pr - 1));
        return s;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> T[i].val;

    // 1) Cartesian 树
    build();
    // 2) Euler 序
    root->dep = 0;
    DFS(root);
    // 3) 分块 + ST 预处理
    ST_init();
    small_init();

    // 每次把原数组位置 l、r 映射为 Euler 序位置 dfn，然后做区间 RMQ
    while (m--) {
        int l, r;               // 原数组中的两个位置（1-based / 0-based 按题意）
        cin >> l >> r;
        // 这里假设 l、r 是 0-based 下标；若是 1-based，改为 T[l-1], T[r-1]
        cout << query(T[l].dfn, T[r].dfn)->val << '\n';
    }
    return 0;
}

Previous Topic

Back to Lesson

Next Topic