一、普通稀疏表的瓶颈

• 空间：如果直接为长度 $n$ 的序列构建完整的稀疏表，通常要开一个大小为 $f[i][k],\quad i=1\ldots n,\;k=0\ldots\lfloor\log_2 n\rfloor$ 的二维数组，空间 $O(n\log n)$。当 $n$ 高达 $2\times10^6$ 时，这几乎要几亿个整数，内存吃紧。

• 时间：构造全部层级也是 $O(n\log n)$，而后每次查询要在稀疏表上再做一次 $O(1)$ 查询，总共仍是 $O(n\log n + n)$。

但本题的查询非常“规律”——我们只要“每个位置 $i$ 前 $m$ 个数”的最小值，而不是随意多次任意区间查询。能不能针对这个“滑动固定窗口”特点做优化？

二、分层构建 + 在线输出

1. “分层”是什么意思？

我们还是按照稀疏表的思路，一层一层地（对应区间长度 $2^0,2^1,2^2,\dots$）合并最小值。但是：

• 只建到 $;2^j\le m;$ 为止——因为我们从来不需要长度超过 $m$ 的区间。
• 一层一层 构建完第 $j$ 层以后，就可以“尽可能地”把所有窗口长度 $\le2^{j+1}$ 的位置答案都算出来——这些都依赖第 $j$ 层和第 $j$ 层合并后的结果。

2. 在线输出的妙处

假设我们已经构建了所有长度 $\le2^j$ 的区间最小值（存储在滚动数组 f[][t] 中），那么任意长度 $L\le2^{j+1}$ 的区间，就可以通过两个 $2^j$ 相邻块求最小值来获得答案：

[min at [L, L+2^j−1],  min at [R−2^j+1, R]]

题目里，我们第 $i$ 行要的区间是 $[,\max(1,i-m),,,i-1,]$，长度记作 $\ell=\min(i-1,m)$。 只要发现 $\ell<2^{j+1}$，就证明“第 $j$ 层”已经足以回答第 $i$ 个结果，于是立刻输出，无需等待更高层。

这样，我们 一边建表（不断增大 $j$），一边把能回答的位置依次打印出来。

• 保证：每个位置只输出一次
• 节省：避免构建完所有层再一次性遍历所有 $i$

三、滚动数组：只要两列

在每一层 $j$，我们只用到“上一层”的结果去合并出“当前层”的结果，完全不需要保留更早的层，因此：

• 用两列 f[][0] 和 f[][1] 交替存储 “上一层” 和 “当前层”
• 每进一层，t ^= 1，新的一列被覆盖再利用

内存从 $O(n\log n)$ → $O(2n)=O(n)$，当 $n=2\times10^6$ 也不过几千万字节。

四、完整流程归纳

1. 预处理 lg2[i] = ⌊log₂ i⌋，$O(n)$。

2. 初始化：第 $j=0$ 层，f[i][t]=arr[i]。同时，输出 $i=1$ 的答案（无前驱，取 $0$）。

3. 按层循环 $j=1,2,\dots$ 直到 $2^j>m$：

   1. 切换滚动索引 t ^= 1
   2. 用 f[][1-t]（上一层）构造 f[][t]（当前层），即 $f[i][t] = \min\bigl(f[i][1-t],\;f[i+2^{j-1}][1-t]\bigr).$
   3. 令 nextLen = 2^{j+1}，只要序号 pos 满足 min(pos−1,m) < nextLen，就能 直接用当前层 f[][t] 回答第 pos 个位置的最小值， 输出后 pos++。

4. 结束：所有 $n$ 个答案都已输出。

五、为什么这么快？

• 时间：最多做 $\sum_j O(n)$ 的合并，$j$ 直到 $\log_2 m$，总体 $O(n\log m)$。输出时又是一趟 $O(n)$，合计 $O(n\log m)$。
• 空间：只存两列，$O(2n)$。

相比每个位置都用单调队列也能 $O(n)$，但单调队列常数更大，而且不利于让同学理解“稀疏表分层合并”的思想；而这种方法把稀疏表和滑动窗口结合，既加深学生对 RMQ 的认识，又用上了滚动数组的经典技巧，综合价值很高。

小结

核心优化：

1. 分层构建到 $2^j\le m$，不必覆盖所有 $\log_2 n$。
2. 边建边答：当当前层能覆盖某个窗口长度时立刻输出，无需等完所有层。
3. 滚动数组：上一层和当前层互相覆盖，只保留两列，空间 $O(n)$。

这样，你既保留了稀疏表的 $O(1)$ 查询思路，又克服了内存和不必要计算的瓶颈。

rmq+滚动数组优化：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2'000'000 + 5;
int n, m;                    // n: 序列长度；m: 前 m 项查询范围
int arr[MAXN];               // 原始序列，1-based
int st[MAXN][2];             // 滚动稀疏表：st[i][k] 存储 “[i, i+2^k?1]” 的最小值
int lg2_[MAXN];              // lg2_[i] = floor(log2(i))
// —— 预处理 lg2 数组 ——
// lg2_[i] = floor(log2(i)), 1 ≤ i ≤ nn
void prec_log(int nn) {
    lg2_[1] = 0;
    for (int i = 2; i <= nn; i++) {
        lg2_[i] = lg2_[i >> 1] + 1;
    }
}
// —— 构建滚动稀疏表某一层 ——
// k: 当前层数，对应区间长度 2^k
// t: 当前要写入 st[][t]
// n: 序列长度
void buildLayer(int k, int n, int t) {
    if (k == 0) {
        // 长度 2^0 = 1，直接拷贝原数组
        for (int i = 1; i <= n; i++) {
            st[i][t] = arr[i];
        }
    } else {
        // 2^k = 2 * 2^(k-1)
        int half = 1 << (k - 1);
        int limit = n - (1 << k) + 1;  // 保证 i + 2^k - 1 ≤ n
        for (int i = 1; i <= limit; i++) {
            st[i][t] = min(st[i][1 - t], st[i + half][1 - t]);
        }
    }
}
// —— 区间最小值查询 ——
// 询问 [L, R] 范围内的最小值，利用当前层 st[][t]
inline int rmq(int L, int R, int t) {
    int len = R - L + 1;
    int k   = lg2_[len];
    int seg = 1 << k;
    return min(st[L][t], st[R - seg + 1][t]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    // 1. 预处理 log2
    prec_log(n);
    // 2. i = 1 时没有前驱，直接输出 0
    printf("0\n");
    int pos = 2;   // 下一次要输出的是 a[pos] 之前 m 项的最小值
    int t   = 0;   // 滚动标记：在 st[][0] 和 st[][1] 之间切换
    // 3. 分层构建并在线输出答案
    for (int k = 0; (1 << k) <= m; k++) {       
        buildLayer(k, n, t);      // 构建第 k 层
        t ^= 1;                   // 切换到当前层
        int nextLen = 1 << (k + 1);
        // 只要当前层能覆盖 pos-1 或 m（取小）的区间，就立刻输出
        while (pos <= n && min(pos - 1, m) < nextLen) {
            int R   = pos - 1;
            int L   = pos - m;
            if (L < 1) L = 1;
            int ans = rmq(L, R, 1-t);
            printf("%d\n", ans);
            pos++;
        }
    }
    return 0;
}

普通rmq稀疏表,80分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000000 + 5;
int n, m;
int a[MAXN];               // 存放输入的序列，1-based
int lg2_[MAXN];            // 记录 floor(log2(i))
int K;                     // 最大的 k，使得 2^k <= n
int *st[MAXN];             // st[i] 指向长度为 (K+1) 的数组，存稀疏表

// 预处理 log2 数组，计算 lg2_[i] = floor(log2(i))
void prec(int nn) {
    lg2_[1] = 0;
    for(int i = 2; i <= nn; i++) {
        lg2_[i] = lg2_[i >> 1] + 1;
    }
    K = lg2_[nn];
}

// 构建稀疏表 st，1-based
// st[i][k] = min(a[i], a[i+1], ..., a[i + 2^k - 1])
void build(int nn) {
    // 给每个 st[i] 分配 (K+1) 大小的空间
    for(int i = 1; i <= nn; i++) {
        st[i] = new int[K + 1];
        st[i][0] = a[i];  // k = 0 时，区间长度 1
    }
    // 逐层构造 k = 1..K
    for(int k = 1; k <= K; k++) {
        int len = 1 << (k - 1);  // 上一层区间长度为 2^(k-1)
        for(int i = 1; i + (1 << k) - 1 <= nn; i++) {
            st[i][k] = min(st[i][k - 1], st[i + len][k - 1]);
        }
    }
}

// 查询区间 [L,R] 的最小值，1-based，下标必须满足 1 ≤ L ≤ R ≤ n
int qmin(int L, int R) {
    int len = R - L + 1;
    int k = lg2_[len];
    int span = 1 << k;  // 2^k
    return min(st[L][k], st[R - span + 1][k]);
}

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

    // 读入 n, m
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 预处理 log2 数组
    prec(n);
    // 构建稀疏表
    build(n);

    // 对每个 i，输出 a[i] 之前 m 个数区间的最小值
    // 如果 i=1，没有前面的数，输出 0
    for(int i = 1; i <= n; i++) {
        if (i == 1) {
            cout << 0 << "\n";
        } else {
            // 计算区间 [L, R]，R = i-1，L = max(1, i-m)
            int R = i - 1;
            int L = i - m;
            if (L < 1) L = 1;
            // 查询并输出
            int ans = qmin(L, R);
            cout << ans << "\n";
        }
    }
    return 0;
}