```cpp
#include<cstdio>
#include<iostream>
using namespace std;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define N 1000001
unsigned int n,m,k,a[N],big[N<<2],sml[N<<2]/*,tag[N<<2]*/;
void init()
{
scanf("%d%d",&n,&k);
m=n-k+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
}
inline void pushup(int p)
{
big[p]=max(big[ls(p)],big[rs(p)]);
sml[p]=min(sml[ls(p)],sml[rs(p)]);
}
void build(int p,int l,int r)
{
//tag[p]=0;
if(l==r)
{
big[p]=sml[p]=a[l];
return;
}
int m=(l+r)>>1;
build(ls(p),l,m);
build(rs(p),m+1,r);
pushup(p);
}
/*
inline void f(int p,int l,int r,int k)
{
tag[p]=tag[p]+k;
ans[p]=ans[p]+k*(r-l+1);
}
inline void pushdown(int p,int l,int r)
{
int m=(l+r)>>1;
f(ls(p),l,m,tag[p]);
f(rs(p),m+1,r,tag[p]);
tag[p]=0;
}
inline void update(int nl,int nr,int l,int r,int p,int k)
{
if(nl<=l&&r<=nr)
{
ans[p]+=k*(r-l+1);
tag[p]+=k;
return;
}
pushdown(p,l,r);
int m=(l+r)>>1;
if(nl<=m)
update(nl,nr,l,m,ls(p),k);
if(m<nr)
update(nl,nr,m+1,r,rs(p),k);
pushup(p);
}
*/
int querymin(int qx,int qy,int l,int r,int p)
{
int res=2147483647;
if(qx<=l&&r<=qy)
return sml[p];
int m=(l+r)>>1;
//pushdown(p,l,r);
if(qx<=m)
res=min(res,querymin(qx,qy,l,m,ls(p)));
if(m<qy)
res=min(res,querymin(qx,qy,m+1,r,rs(p)));
return res;
}
int querymax(int qx,int qy,int l,int r,int p)
{
int res=0;
if(qx<=l&&r<=qy)
return big[p];
int m=(l+r)>>1;
//pushdown(p,l,r);
if(qx<=m)
res=max(res,querymax(qx,qy,l,m,ls(p)));
if(m<qy)
res=max(res,querymax(qx,qy,m+1,r,rs(p)));
return res;
}
int main()
{
init();
build(1,1,n);
for(int i=1;i<=m;i++)
{
printf("%d ",querymin(i,i+k-1,1,n,1));
}
putchar('\n');
for(int i=1;i<=m;i++)
{
printf("%d ",querymax(i,i+k-1,1,n,1));
}
return 0;
}
```
by wxwoo @ 2019-03-02 12:38:08
~~去你的刚学OI~~
by wxy_god @ 2019-03-02 12:38:27
# ~~去你的萌新~~
by t162 @ 2019-03-02 12:38:38
刚学OI？
~~去你的萌新~~
by aminoas @ 2019-03-02 12:38:55
~~话说这题用单调队列最好吧~~
by xunJason @ 2019-03-02 12:39:44
@[Bambusoideae](/space/show?uid=106140) @[我是一个垃圾](/space/show?uid=89396)
dalao别装弱啊...帮我看看错吗哪了qwqwq
by wxwoo @ 2019-03-02 12:40:10
我还是拿手机敲的线段树板子啊qwqwq
by wxwoo @ 2019-03-02 12:43:01
我真的不会线段树...
by wxy_god @ 2019-03-02 12:44:38
建议学学正解单调队列。
线段树我觉得可能会T，毕竟常数大，复杂度也大
by AC_Automation @ 2019-03-02 12:46:06
ST表也行吧
by xunJason @ 2019-03-02 12:47:12