暴力做法

枚举呗……时间复杂度$O(n^2)$。
显然，这种复杂度不是我们可以接受的

线段树做法

ps：感觉这东西还是暴力……
由于这道题目问的是区间的最大值和最小值，所以我们可以用线段树去解决。（只有查询，可好敲了）但是呢，由于线段树的复杂度是$O(nlogn)$的，而且ta常数比较大，所以会超时qwq
附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<malloc.h> 
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

struct tree{
    int maxx,minn;
    tree *lson,*rson;
}*root = (tree*)malloc(sizeof(tree));

struct node{
    int a,b;
}ans[1000005];

void build(tree *tre,int l,int r)
{
    if(l == r)
    {
        tre -> maxx = read();
        tre -> minn = tre -> maxx;
        return;
    }
    int mid = (l + r) >> 1;
    tree *son1 = (tree*)malloc(sizeof(tree));
    tree *son2 = (tree*)malloc(sizeof(tree));
    tre -> lson = son1;
    tre -> rson = son2;
    build(tre -> lson,l,mid);
    build(tre -> rson,mid + 1,r);
    tre -> maxx = max(tre -> lson -> maxx,tre -> rson -> maxx);
    tre -> minn = min(tre -> lson -> minn,tre -> rson -> minn);
}

node query(tree *tre,int l,int r,int x,int y)
{
    if(l == r) return (node){tre -> maxx,tre -> minn};
    int mid = (l + r) >> 1;
    node t1,t2;
    t1.a = -INF; t1.b = INF; t2.a = -INF; t2.b = INF;
    if(x <= mid) t1 = query(tre -> lson,l,mid,x,y);
    if(y > mid) t2 = query(tre -> rson,mid + 1,r,x,y);
    return (node){max(t1.a,t2.a),min(t1.b,t2.b)};
}

int main()
{
    int n,k;
    n = read(); k = read();
    build(root,1,n);
    for(int i = 1; i <= n - k + 1; i++) ans[i] = query(root,1,n,i,i + k - 1);
    for(int i = 1; i <= n - k + 1; i++) printf("%d ",ans[i].b); printf("\n");
    for(int i = 1; i <= n - k + 1; i++) printf("%d ",ans[i].a); printf("\n");
    return 0;
}

单调队列做法

终于到正解了……
~~直接用单调队列瞎搞一下就可以啦，~~时间复杂度是$O(n)$的
对于每次入队，我们都要判断一下，如果该数大于队尾，则直接入队，否则将队列中所有比ta小的数字全部出队，然后再入队，这样就能保证队列的单调性。
对于每次出队，我们都要判断一下要出队的元素是否还在队列中（可能在别的元素入队的时候出队了）
附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,k,a[1000005],que[1000006],head=1,tail;

void q_push1(int k)
{
    if(head > tail)
    {
        que[++tail] = k;
        return ;
    }
    if(k <= que[tail]) 
    {
        que[++tail] = k;
        return ;
    }
    while(que[tail] < k && tail >= head) tail--;
    que[++tail] = k;
}

void q_push2(int k)
{
    if(head > tail)
    {
        que[++tail] = k;
        return ;
    }
    if(k >= que[tail])
    {
        que[++tail] = k;
        return ;
    }
    while(que[tail] > k && tail >= head) tail--;
    que[++tail] = k;
}

int main()
{
    n = read(); k = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++)
    {    
        if(i - k > 0)
            if(a[i - k] == que[head])
                head ++;
        q_push2(a[i]);
        if(i >= k)printf("%d ",que[head]);
    }
    printf("\n");
    head = 1; tail = 0;
    for(int i = 1; i <= n; i++)
    {    
        if(i - k > 0)
            if(a[i - k] == que[head])
                head ++;
        q_push1(a[i]);
        if(i >= k)printf("%d ",que[head]);
    }
    return 0;
}