RMQ稀疏表

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int MAXK = 17 + 1; // 2^17 = 131072 > 100000

int n, k;
int a[MAXN];
int lg2[MAXN];
int stMX[MAXK][MAXN];
int stMN[MAXK][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 读入 n, k
    cin >> n >> k;
    // 读入数组 a[1..n]
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        stMX[0][i] = a[i]; // 长度 2^0=1 的区间最大
        stMN[0][i] = a[i]; // 长度 2^0=1 的区间最小
    }
    // 预处理对数表：lg2[i] = floor(log2(i))
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    // 构建稀疏表：stMX[k][i]、stMN[k][i] 表示从 i 开始长度 2^k 的区间最大/最小
    for (int t = 1; t <= MAXK; t++) {
        int len = 1 << (t - 1);
        if (len * 2 > n) break;
        for (int i = 1; i + (len * 2) - 1 <= n; i++) {
            stMX[t][i] = max(stMX[t - 1][i], stMX[t - 1][i + len]);
            stMN[t][i] = min(stMN[t - 1][i], stMN[t - 1][i + len]);
        }
    }
    // 对每个滑动窗口 [i, i+k-1] 做查询
    int times = n - k + 1;
    for (int i = 1; i <= times; i++) {
        int span = k;
        int t = lg2[span];
        int len = 1 << t;
        int r = i + span - 1;
        // 最大值 = max(区间 [i, i+len-1], [r-len+1, r])
        int mx = max(stMX[t][i], stMX[t][r - len + 1]);
        int mn = min(stMN[t][i], stMN[t][r - len + 1]);
        cout << mx << " " << mn << "\n";
    }
    return 0;
}

双端队列：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

// 全局变量：n=元素个数，k=窗口大小，a[]=输入序列
int n, k;
int a[MAXN];

// 双端队列 dq1 用于维护当前窗口的最大值索引，dq2 用于维护当前窗口的最小值索引
deque<int> dq1, dq2;

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

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

    // 先处理前 k-1 个元素，准备好初始窗口前的 deque 状态
    for (int i = 1; i < k; i++) {
        // 维护最大队列 dq1：将当前 i 的元素放到队尾前，弹出所有比 a[i] 小的下标
        while (!dq1.empty() && a[dq1.back()] <= a[i]) {
            dq1.pop_back();
        }
        dq1.push_back(i);

        // 维护最小队列 dq2：将当前 i 的元素放到队尾前，弹出所有比 a[i] 大的下标
        while (!dq2.empty() && a[dq2.back()] >= a[i]) {
            dq2.pop_back();
        }
        dq2.push_back(i);
    }

    // 从 i=k 到 i=n，一次推进窗口，输出每个窗口的最大和最小
    for (int i = k; i <= n; i++) {
        // 1) 把第 i 个元素加入两个 deque
        // 加入 dq1（维护最大值）：弹出队尾所有 a[*] <= a[i]
        while (!dq1.empty() && a[dq1.back()] <= a[i]) {
            dq1.pop_back();
        }
        dq1.push_back(i);
        // 加入 dq2（维护最小值）：弹出队尾所有 a[*] >= a[i]
        while (!dq2.empty() && a[dq2.back()] >= a[i]) {
            dq2.pop_back();
        }
        dq2.push_back(i);

        // 2) 确保 dq1.front() 和 dq2.front() 都在当前窗口 [i-k+1, i] 范围内
        int L = i - k + 1;
        while (!dq1.empty() && dq1.front() < L) {
            dq1.pop_front();
        }
        while (!dq2.empty() && dq2.front() < L) {
            dq2.pop_front();
        }

        // 3) 此时，dq1.front() 对应的是当前窗口的最大值下标
        //    dq2.front() 对应的是当前窗口的最小值下标
        int mx = a[dq1.front()];
        int mn = a[dq2.front()];
        // 输出“最大 最小”并换行
        cout << mx << " " << mn << "\n";
    }

    return 0;
}