@[Lolierl](/space/show?uid=22930) segment tree
by decoqwq @ 2018-05-01 20:42:17
@[刘浩宇（寂）](/space/show?uid=48265)
可以不用啊
by Lolierl @ 2018-05-01 20:45:51
@[Lolierl](/space/show?uid=22930) 建议了解一下正宗的单调队列姿势
by つきみやあゆ @ 2018-05-01 20:48:01
@[Lolierl](/space/show?uid=22930)
我刚才copy了你的代码，然后做了一些改动：
1. 把$l$指针和$r$指针**初始值**都赋值为$1$
2. 由于我开数组向来都**比较大**，所以顺手把$a$数组的大小和$b$数组的大小都开为$n + 10$
主题思路并没有什么问题。
以上
将改好的代码顺便贴一下吧：
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int MAX=2147483647;
struct h
{
int x;
int num;
};
int main()
{
int n,k;
cin>>n>>k;
int a[n+10];
for(int i=1;i<=n;i++)
cin>>a[i];
h b[n + 10];
int l=1,r=1;
for(int i=1;i<=k;i++)b[i].x=MAX;
for(int i=1;i<=k;i++)
{
while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
r++;b[r].x=a[i];b[r].num=i;
/*cout<<a[i]<<endl;
for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
cout<<endl;*/
}
/*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
cout<<endl;*/
cout<<b[l].x<<' ';
for(int i=k+1;i<=n;i++)
{
if(b[l].num<=i-k)l++;
while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
r++;b[r].x=a[i];b[r].num=i;
cout<<b[l].x<<' ';
/*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
cout<<endl;*/
}
cout<<endl;
l=1,r=1;
for(int i=1;i<=k;i++)b[i].x=-MAX;
for(int i=1;i<=k;i++)
{
while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
r++;b[r].x=a[i];b[r].num=i;
}
cout<<b[l].x<<' ';
for(int i=k+1;i<=n;i++)
{
if(b[l].num<=i-k)l++;
while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
r++;b[r].x=a[i];b[r].num=i;
cout<<b[l].x<<' ';
}
return 0;
}
```
题外话：
~~虽然不开氧气优化这份代码跑得挺快，但是在氧气优化的环境下，还是$STL$的双端队列快~~
~~所以安利一发我写的双端队列的博客[求点赞](https://www.luogu.org/blog/yjx/p1886-hua-dong-chuang-kou)~~
by yjxyjx @ 2018-05-01 21:20:13
@[yjxyjx](/space/show?uid=51211)
谢大佬
by Lolierl @ 2018-05-04 17:22:40