难度： 黄

算法： 线段树，ST 表，单调队列等数据结构

比较板子的题。

ST 表代码：

#include<bits/stdc++.h>
using namespace std;
struct max_st{
	int f[1000010][25],n;
	int que(int x,int y){
		int p=log2(y-x),d=1<<p;
		return max(f[x][p],f[y-d+1][p]);
	}
	void init(queue<int> q){
		while(!q.empty()){
			f[++n][0]=q.front();
			q.pop();
		}
		for(int j=1,k=2;k<=n;k*=2,j++){
			for(int i=1;i<=n;i++){
				f[i][j]=que(i,i+k-1);
			}
		}
	}
}t1;
struct min_st{
	int f[100010][20],n;
	int que(int x,int y){
		int p=log2(y-x),d=1<<p;
		return min(f[x][p],f[y-d+1][p]);
	}
	void init(queue<int> q){
		while(!q.empty()){
			f[++n][0]=q.front();
			q.pop();
		}
		for(int j=1,k=2;k<=n;k*=2,j++){
			for(int i=1;i+k-1<=n;i++){
				f[i][j]=que(i,i+k-1);
			}
		}
	}
}t2;
int n,x,k;
queue<int> q1,q2;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		q1.push(x);
		q2.push(x);
	}
	t1.init(q1);
	t2.init(q2);
	for(int i=1;i+k-1<=n;i++){
		printf("%d %d\n",t1.que(i,i+k-1),t2.que(i,i+k-1));
	}
}