题解
经典的单调队列入门题。
思路很简单，就是先判断队头是否“过期”，然后再在队尾进行比较。
这里的代码是可以进行空间上的优化的。
注意一个点：$k=1$时最好特判。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n,k,a[1000005],d1[1000005][2],d2[1000005][2],
f1=0,f2=0,r1=1,r2=1,ans[1000005][2];
void in(int at,int p){
while(r1>f1&&d1[f1][1]<=at-k)
f1++;
while(r2>f2&&d2[f2][1]<=at-k)
f2++;
while(r1>f1&&d1[r1-1][0]>p)
d1[r1-1][0]=d1[r1-1][1]=0,r1--;
while(r2>f2&&d2[r2-1][0]<p)
d2[r2-1][0]=d2[r2-1][1]=0,r2--;
d1[r1][0]=p,d1[r1++][1]=at;
d2[r2][0]=p,d2[r2++][1]=at;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
i=(k==1)?0:1;
d1[0][0]=d2[0][0]=a[0];
d1[0][1]=d2[0][1]=0;
for(;i<n;i++){
in(i,a[i]);
ans[i][0]=d1[f1][0];
ans[i][1]=d2[f2][0];
}
for(i=k-1;i<n-1;i++)
printf("%d ",ans[i][0]);
printf("%d\n",ans[n-1][0]);
for(i=k-1;i<n-1;i++)
printf("%d ",ans[i][1]);
printf("%d\n",ans[n-1][1]);
return 0;
}