#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
T X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
if(flag) return X;
return ~(X-1);
}
template<typename T=int>
inline void write(T X){
if(X<0) putchar('-'),X=~(X-1);
T s[20],top=0;
while(X) s[++top]=X%10,X/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar('\n');
}
const int N=1e5+5,Log=35,log=30;
int n,m;
int a[N];
int lg[Log],f[N][Log];
void init(int *a,int n){
lg[0]=-1;
for(int i=1; i<=n; i++) f[i][0]=a[i],lg[i]=lg[i>>1]+1;
for(int j=1; j<=log; j++)
for(int i=1; i+(1<<j)-1<=n; i++)
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int main(){
n=read(),m=read();
for(int i=1; i<=n; i++) a[i]=read();
init(a,n);
for(int l=1,r=m; r<=n; l++,r++){
int x=lg[r-l+1];
// printf("%d %d min(%d,%d): ",l,r,f[l][x],f[r-(1<<x)+1][x]);
write(min(f[l][x],f[r-(1<<x)+1][x]));
}
return 0;
}
第一组数据错了:
1000 782
...
标准输出全部是 35,这个代码输出 6,6,7,…,7,8,…,8,9,…,9,35,…,35 awa