【题目描述】

【输入】

【输出】

【输入样例】

5 3
1 2 3 4 5

【输出样例】

3 1
4 2
5 3

【提示】

题目分析

本题是极其经典的静态区间最值查询（RMQ）模型。 给定一个长度为 N 的序列，要求一个长度为 K 的窗口从左向右滑动，每次输出窗口内包含的 K 个元素的最大值和最小值。

核心特征：

1. 纯静态查询：序列在初始化后没有任何修改操作，只有查询。

2. 高频次查询：一共需要进行 N−K+1 次区间最值查询。

3. 数据范围：1≤K≤N≤10^5，且序列元素横跨整个 32 位有符号整型 [−2^31,2^31−1]。

解题思路与思考过程

面对纯静态的 RMQ 问题，最正统的两种数据结构打法分别是ST表和线段树。

• 路径一（ST表）：既然没有修改操作，优先考虑利用倍增思想预处理。预处理虽然花费 O(NlogN)，但查询能达到极致的 O(1)。面对高频查询，ST 表是绝对的性能王者。为了方便后续扩展或查具体位置，ST 表内部存最值的“下标”比直接存“数值”更具普适性。

• 路径二（线段树）：用分治思想将序列转化为树形结构。建树极快，但每次查询需要从根节点向下探索，时间复杂度为 O(logN)。虽然常数略大，但它是所有区间问题的万能基座，逻辑极其严密。

算法设计

1. ST 表（倍增法）

• 状态定义：设 ma[i][j] 表示从下标 i 开始，长度为 2^j 的区间内的最大值下标。

• 状态转移：将长度为 2^j 的区间，从中间劈开，变成两个长度为 2^(j−1) 的区间。 即：比较 [i, i+2^(j-1)-1] 和 [i+2^(j-1), i+2^j-1] 这两段的最值。

• O(1) 查询：查询区间 [L,R] 时，找到一个最大的k，使得 2^k≤R−L+1。然后分别从 L 往右取长度 2^k，从 R 往左取长度 2^k。这两段必然能完全覆盖目标区间，取两者的最值即可。

2. 线段树（分治法）

• 节点结构：每个节点管辖一段物理区间 [l,r]，维护该区间内的 ma（最大值）和 mi（最小值）。

• 向上合并 (pushup)：父节点的最值严格等于左儿子和右儿子最值中的最值。

• 区间查询 (query)：

  • 完全包含：直接返回当前节点维护的值。

  • 完全不相交：返回极其安全的越界兜底值（最大值兜底负无穷，最小值兜底正无穷）。

  • 部分相交：递归向左右子树索要答案并合并。

时空复杂度分析

算法	预处理/建树时间	单次查询时间	整体时间复杂度	空间复杂度
ST表	O(NlogN)	O(1)	O(NlogN+M)	O(NlogN)
线段树	O(N)	O(logN)	O(N+MlogN)	O(N)
(注：本题中查询次数 M=N−K+1)

坑点总结：

1. log2() 的浮点运算陷阱（ST表致命伤）： 在 ST 表的 O(1) 查询中，如果直接使用 <cmath> 库的 log2() 函数，会引入极其耗时的浮点数运算指令，导致查询性能断崖式下跌。 优化：可以选择替换为 C++ 内置的硬件级位运算函数 __lg(),我代码中还是以log2()为例。

2. 绝对极值的越界与溢出（线段树致命伤）： 数据下限达到了 −2^31。如果不使用 long long 类型的无穷大 30000000000LL，或者错误地使用 0 作为越界兜底值，会在遇到全负数数据时发生“最大值被篡改为 0”的惨剧。 正解：明确定义带有 LL 后缀的超大常量 INF，且求最大值越界必须返回 -INF，求最小值越界必须返回 INF。

核心代码与完整注释

版本一：ST表

//st表
#include <iostream>
#include <cmath>
using namespace std;
int n,kk;
long long a[100010];//原数字串
//ma[i][j]表示以i为起点的长度为2^j的区间的最大值的下标
int ma[100010][20];
//mi[i][j]表示以i为起点的长度为2^j的区间的最小值的下标
int mi[100010][20];

//预处理st表
void pre(){
    //每一段区间长度为1的最大值的下标为自己
    for(int i=1;i<=n;i++) ma[i][0]=i;
    //每一段区间长度为1的最小值的下标为自己
    for(int i=1;i<=n;i++) mi[i][0]=i;

    //外层循环枚举区间长度的指数j
    for(int j=1;(1<<j)<=n;j++){
        //内层循环枚举起点i 确保右端点i+2^j-1不越界
        for(int i=1;i+(1<<j)-1<=n;i++){
            //区间长度的一半
            int tmp=1<<(j-1);
            //状态转移 比较左半边和右半边的最大值
            if(a[ma[i][j-1]]>a[ma[i+tmp][j-1]])
                ma[i][j]=ma[i][j-1];
            else
                ma[i][j]=ma[i+tmp][j-1];

            //状态转移 比较左半边和右半边的最小值
            if(a[mi[i][j-1]]<a[mi[i+tmp][j-1]])
                mi[i][j]=mi[i][j-1];
            else
                mi[i][j]=mi[i+tmp][j-1];
        }
    }
}

//区间查询
void query(int l,int r){
    int k=log2(r-l+1);
    int tmp=1<<k;//找出一个最大的2^k长度
    //从左端点向右取2^k 从右端点向左取2^k 两段必然完全覆盖[l,r]
    //先输出最大值
    cout<<max(a[ma[l][k]],a[ma[r-tmp+1][k]])<<" ";
    //再输出最小值
    cout<<min(a[mi[l][k]],a[mi[r-tmp+1][k]]);
} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>kk;
    for(int i=1;i<=n;i++) cin>>a[i];
    //先进行预处理 得到ma mi数组
    pre();
    //查询
    for(int i=1;i+kk-1<=n;i++){
        query(i,i+kk-1);
        cout<<"\n";
    }
}

版本二：线段树

//线段树做法
#include <iostream>
using namespace std;
int n,k;
const int maxn=100010;
const long long INF=30000000000ll;
int a[maxn];//原数列

//线段树节点
struct node{
    int ma;//区间最大值
    int mi;//区间最小值
}tree[maxn<<2];

//向上汇总信息 父节点=max/min(左儿子,右儿子)
void pushup(int rt){
    tree[rt].ma=max(tree[rt<<1].ma,tree[rt<<1|1].ma);
    tree[rt].mi=min(tree[rt<<1].mi,tree[rt<<1|1].mi);
}

//当前节点为rt 当前节点管辖区间为[l,r]
void build(int l,int r,int rt){
    if(l==r){//到达物理叶子节点
        tree[rt].ma=a[l];
        tree[rt].mi=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);//儿子建完后 更新父亲
}

//最大值查询
//线段树查询 当前查询区间是[L,R] 当前节点是rt 当前节点
//管辖区间是[l,r]
long long query1(int L,int R,int l,int r,int rt){
    //目标完全包围当前区间 直接提取当前区间数据
    if(L<=l&&R>=r) return tree[rt].ma;
    //这里不能return 0 因为序列有正数有负数 最大值完全可能小于0
    //所以要返回一个极小值
    if(r<L||l>R) return -INF;
    int mid=(l+r)>>1;
    //找最大值 因为每个数可能为负 所以初始化一个极大的负数
    //所以要返回一个极小值
    long long ans=-INF;
    //如果目标和左边区间有覆盖 去左边
    if(L<=mid) ans=max(ans,query1(L,R,l,mid,rt<<1));
    //如果目标和右边区间有覆盖 去右边
    if(R>mid) ans=max(ans,query1(L,R,mid+1,r,rt<<1|1));
    return ans;
}
//最小值查询
//线段树查询 当前查询区间是[L,R] 当前节点是rt 当前节点
//管辖区间是[l,r]
long long query2(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r) return tree[rt].mi;
    //这里不能return 0 因为序列有正数有负数 最小值完全可能大于0
    //所以要返回一个极大值
    if(r<L||l>R) return INF;
    int mid=(l+r)>>1;
    //找最小值 所以初始化一个极大的数
    long long ans=INF;
    if(L<=mid) ans=min(ans,query2(L,R,l,mid,rt<<1));
    if(R>mid) ans=min(ans,query2(L,R,mid+1,r,rt<<1|1));
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    //建树
    build(1,n,1);
    //查询
    for(int i=1;i+k-1<=n;i++){
        //查最大值
        cout<<query1(i,i+k-1,1,n,1)<<" ";
        //查最小值
        cout<<query2(i,i+k-1,1,n,1)<<"\n";
    }
    return 0;
}