@[mysterys](/user/659165) O2可过
```cpp
#include<bits/stdc++.h>
#define int long long
#define MAXN 2000006
using namespace std;
int n,m;
int a[MAXN];
struct node{
int minn,l,r;
}tree[MAXN<<2];
void build(int u,int l,int r){
tree[u].l=l;
tree[u].r=r;
if(l==r){
tree[u].minn=a[l];
return;
}
int m=(l+r)>>1;
build(u<<1,l,m);
build(u<<1|1,m+1,r);
tree[u].minn=min(tree[u<<1].minn,tree[u<<1|1].minn);
}
int query(int u,int l,int r){
if(tree[u].l>=l&&tree[u].r<=r){
return tree[u].minn;
}
int m=(tree[u].l+tree[u].r)>>1;
int ans=1e9;
if(l<=m){
ans=min(query(u<<1,l,r),ans);
}
if(r>m){
ans=min(query(u<<1|1,l,r),ans);
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=n;i++){
int x_x=i-m,y_y=i-1;
if(x_x<=0) x_x=1;
if(x_x>y_y){
printf("0\n");
continue;
}
printf("%lld\n",query(1,x_x,y_y));
}
return 0;
}
```
by zyh0516_lucky @ 2024-02-17 19:00:11
@[mysterys](/user/659165) 线段树固然重要,但在考场上,能用单调队列,就用单调队列,因为线段树相比慢
by zyh0516_lucky @ 2024-02-17 19:01:19