#include <cstdio>

const int MAXN = 1000000;

int q[MAXN + 1], min[MAXN + 1], max[MAXN + 1];
int n,k;

void input()
{
int i;
scanf("%d %d",n, &k);
for (i = 1; i <= n; i++)
scanf("%d",q[i]);
}

int BSearchMin(int l, int r, int value)
/* 在一个维护最小值的单调队列min[]中二分查找位置k,使得q[min[k]]>= value */
{
if (value <= q[min[l]]) return l;
for ( ; l < r; )
{
int mid = (l + r) >> 1;
if (q[min[mid]] < value) l = mid + 1;
else r = mid;
}
return r;
}

void MaintainMin()
{
int i, rank;
int Minhead, Mintail;
Minhead = Mintail = 1;
min[Minhead] = 1;
for (i = 2; i <= n; i++)
{
if (q[i] > q[min[Mintail]]) Mintail++;
else
{
rank = BSearchMin(Minhead, Mintail, q[i]);
/* 因为在q[min[Minhead..Mintail]]里面的元素是单调递增的 */
Mintail = rank;
/* 实现满足q[min[]]>= value 的元素的删除 */
}
min[Mintail] = i;
if (i < k) continue;
while (i - min[Minhead] >= k) Minhead++;
/* 如果当前单调队队列min中的队首元素q[min[Minhead]]不在考虑区间范围,出列 */
if (i == n) continue;
printf("%d ",q[min[Minhead]]);
}
printf("%d\n",q[min[Minhead]]);
}

int BSearchMax(int l, int r, int value)
/* 在一个维护最小值的单调队列max[]中二分查找位置k,使得q[max[k]]<= value */
{
if (value >= q[max[l]]) return l;
for ( ; l < r; )
{
int mid = (l + r) >> 1;
if (q[max[mid]] > value) l = mid + 1;
else r = mid;
}
return r;
}

void MaintainMax()
{
int i, rank;
int Maxhead, Maxtail;
Maxhead = Maxtail = 1;
max[Maxhead] = 1;
for (i = 2; i <= n; i++)
{
if (q[i] < q[max[Maxtail]]) Maxtail++;
else
{
rank = BSearchMax(Maxhead, Maxtail, q[i]);
/* 因为在q[max[Minhead..Mintail]]里面的元素是单调递减的 */
Maxtail = rank;
/* 实现满足q[max[]]<= value 的元素的删除 */
}
max[Maxtail] = i;
if (i < k) continue;
while (i - max[Maxhead] >= k) Maxhead++;
/* 如果当前单调队队列max中的队首元素q[max[Maxhead]]不在考虑区间范围,出列 */
if (i == n) continue;
printf("%d ",q[max[Maxhead]]);
}
printf("%d\n",q[max[Maxhead]]);
}

int main()
{
input();
MaintainMin();
MaintainMax();
return 0;
}

不知道为什么提交上去WA。。
还有要不是给了头文件为#include <cstdio>
要是改为#include <iostream>
using namespace std;
就会出现编译错误。。。不知道为什么