```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<const size_t len,const bool mode,typename Tp_>
struct ddqueue{
Tp_ datas[len];
int head,tail;
ddqueue(){
memset(datas,0,sizeof(datas));
head=tail=0;
}
inline int size() { return this->tail - this->head; }
inline bool empty() { return this->head==this->tail; }
inline void push_back(Tp_ data){ this->datas[++this->tail]=data; }
inline void pop_front() { this->head++; }
inline void pop_back() { this->tail--; }
inline void clear() { while (this->size()) this->pop_back(); }
inline Tp_ front() { return this->datas[this->head+1]; }
inline Tp_ end() { return this->datas[this->tail]; }
inline void push(Tp_ data)
{
if (mode)//单调递减，队头最大
{
while (data < this->end()&&(!this->empty())) { this->pop_back(); }
push_back(data);
}
else
{
while (data > this->end()&&(!this->empty())) { this->pop_back(); }
push_back(data);
}
}
};
struct node{
int num,id;
inline friend bool operator > (const node &a,const node &b)
{
return a.num > b.num;
}
inline friend bool operator < (const node &a,const node &b)
{
return a.num < b.num;
}
};
ddqueue<100001,false,node> Greater;
ddqueue<100001,true,node> Less;
int a[100001],n,k;
int main()
{
scanf("%d%d",&n,&k);
for (register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (register int i=1;i<=k-1;i++)
{
Less.push((node){a[i],i});
}
for (register int i=k;i<=n;i++)
{
if (Less.front().id == i-k) Less.pop_front();
//Less.print();
Less.push((node){a[i],i});
printf("%d ",Less.front().num);
}
printf("\n");
for (register int i=1;i<=k-1;i++)
{
Greater.push((node){a[i],i});
}
for (register int i=k;i<=n;i++)
{
if (Greater.front().id == i-k) Greater.pop_front();
Greater.push((node){a[i],i});
printf("%d ",Greater.front().num);
}
printf("\n");
return 0;
}
```
by Jelly_Goat @ 2019-05-30 17:57:08
[自闭](https://www.luogu.org/recordnew/show/19482641)了
by Jelly_Goat @ 2019-05-30 17:57:41
~~暗示五色旗，举报了~~
by SSerxhs @ 2019-05-30 18:05:32
@[SSerxhs](/space/show?uid=29826)
...`五色旗`是什么
是那个什么中国近代用的海军旗帜？？？
by Jelly_Goat @ 2019-05-30 18:07:57
~~换线段树吧，虽然我知道线段树不是正解~~
by wxwoo @ 2019-05-30 18:11:51
@[wxwoo](/space/show?uid=116659) +1
by 逃课小姐MS @ 2019-05-30 18:13:02
~~不对，不带修改应该用ST表，虽然我知道ST表也不是正解~~
by wxwoo @ 2019-05-30 18:14:18
正解：LCT
by 斯茂 @ 2019-05-30 18:19:10
开花(
by Celestial_Scarlet @ 2019-05-30 18:23:06
我P代码只有不到1kb啊qwq
by Celestial_Scarlet @ 2019-05-30 18:24:10