树状数组版本
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000005
int n,k,a[N],MaxTree[N],MinTree[N];
int lowbit(int x){return x & (-x);}
int modify(int x,int y){
for (;x <= n;x += lowbit(x)){
MaxTree[x] = std::max(MaxTree[x],y);
MinTree[x] = std::min(MinTree[x],y);
}
}
int FindMin(int x,int y){
if (y > x){
if (y - lowbit(y) > x) return std::min(MinTree[y],FindMin(x,y - lowbit(y)));
else return std::min(a[y],FindMin(x,y - 1));
}
return a[x];
}
int FindMax(int x,int y){
if (y > x){
if (y - lowbit(y) > x) return std::max(MaxTree[y],FindMax(x,y - lowbit(y)));
else return std::max(a[y],FindMax(x,y - 1));
}
return a[x];
}
int main(){
scanf("%d%d",&n,&k);
memset(MinTree,0x3f,sizeof(MinTree));
memset(MaxTree,0xc0,sizeof(MaxTree));
for (int i = 1;i <= n;i++) scanf("%d",&a[i]),modify(i,a[i]);
for (int i = k;i <= n;i++) printf("%d ",FindMin(i - k + 1,i));
putchar('\n');
for (int i = k;i <= n;i++) printf("%d ",FindMax(i - k + 1,i));
putchar('\n');
return 0;
}
速度速度速度速度