题解 | 信息学奥赛一本通-最敏捷的机器人

既然要最快，本文只介绍线性做法

最简单的做法当然是滑动窗口，单调队列维护

单调队列中的元素单调上升/下降，主要的思想就是

如果位置i比位置j靠后，且比j大/小，那j就是没用的，可以弹出

#include<iostream>
#include<cstdio>
const int maxn=1000100;
using namespace std;

int a[maxn],maxx[maxn],minn[maxn];
int n,k;

int ans[maxn<<2];int cnt=0;

inline void work1(){
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&maxx[h]+k<=i)
            h++;
        while(h<=t&&a[i]<a[maxx[t]])
            t--;
        maxx[++t]=i;
        if(i>=k)
            ans[++cnt]=a[maxx[h]];
    }
}

inline void work2()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&minn[h]+k<=i)
            h++;
        while(h<=t&&a[i]>a[minn[t]])
            t--;
        minn[++t]=i;
        if(i>=k)
            ans[++cnt]=a[minn[h]];
    }
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    work1();
    work2();
    for(int i=1;i<=cnt/2;i++){
        cout<<ans[i+cnt/2]<<' '<<ans[i]<<endl;
    }
    return 0;
}

因为n为1e5，所以也可以用nlogn的方法维护，如ST表等

当然我们也有On的RMQ算法...如笛卡尔树和分块ST表