AC自动机 @ 2017-11-06 23:18:46
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<math.h>
using namespace std;
int a[2000005];
int dp[2000005][21];
inline int query(int a,int b){
int m=log2(b-a+1);
return min(dp[a][m],dp[b-(1<<m)+1][m]);
}
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main(){
std::ios::sync_with_stdio(false);
register int n,m;
n=read(); m=read();
for(register int i=1;i<=n;i++){
a[i]=read();
dp[i][0]=a[i];
}
int fuck=log2(n);
for(register int j=1;j<=fuck;j++){
for(register int i=1;i+(1<<j)<=n;i++){
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int now=1;
while(1){
// int a,b;
// cin>>a>>b;
// cout<<query(a,b)<<endl;
if(now==n+1)return 0;
//cout<<now<<' ';
if(now==1){
cout<<0<<endl;
now++;
}
else if(now<=m){
write(query(1,now-1));
putchar('\n');
now++;
}
else {
write(query(now-m,now-1));
putchar('\n');
now++;
}
}
}
by fy0123 @ 2017-11-06 23:42:13
单调队列可是o(n)的w
by AC自动机 @ 2017-11-07 00:08:57
@bestFy 这么神奇,谢谢啊!又要自学一波了XD
by fy0123 @ 2017-11-07 00:12:37
@FangHaosb 去看看题解吧有写