开了o2线段树跑的飞快（最慢500ms）也没怎么卡常，请求加强数据qwq。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int

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

const int N=1e6+5;

int tree_min[N<<2],tree_max[N<<2],n,k,ans;
int a[N];

void build(int now,int l,int r){
	if(l==r){
		tree_min[now]=a[l],tree_max[now]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid),build(now<<1|1,mid+1,r);
	tree_max[now]=tree_max[now<<1]>tree_max[now<<1|1]?tree_max[now<<1]:tree_max[now<<1|1];
	tree_min[now]=tree_min[now<<1]<tree_min[now<<1|1]?tree_min[now<<1]:tree_min[now<<1|1];
}

void query_min(int now,int l,int r,int x,int y){
	if(l>y||r<x)return;
	if(l>=x&&r<=y){
		ans=ans<tree_min[now]?ans:tree_min[now];
		return;
	}
	int mid=(l+r)>>1;
	query_min(now<<1,l,mid,x,y),query_min(now<<1|1,mid+1,r,x,y); 
}

void query_max(int now,int l,int r,int x,int y){
	if(l>y||r<x)return;
	if(l>=x&&r<=y){
		ans=ans>tree_max[now]?ans:tree_max[now];
		return;
	}
	int mid=(l+r)>>1;
	query_max(now<<1,l,mid,x,y),query_max(now<<1|1,mid+1,r,x,y); 
}

int main(){
	n=read(),k=read();
	for(ri i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	for(ri i=1;i<=n-k+1;i++){
		int l=i,r=i+k-1;
		ans=2100000000,query_min(1,1,n,l,r);
		printf("%d ",ans);
	}
	printf("\n");
	for(ri i=1;i<=n-k+1;i++){
		int l=i,r=i+k-1;
		ans=-2100000000,query_max(1,1,n,l,r);
		printf("%d ",ans);
	}
	return 0;
}