MANCHERSTER @ 2017-08-24 08:12:17
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2000001;
int dp[maxn][20];
int n,m;
void ST(){
int i,j;
for(j=1;(1<<j)<=n;j++){
for(i=1;i+(1<<j)-1<=n;i++){
if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1]){
dp[i][j]=dp[i][j-1];
}
else{
dp[i][j]=dp[i+(1<<(j-1))][j-1];
}
}
}
}
int RMQ(int L,int R){
int len=R-L+1;
int k=0;
while((1<<(k+1)<=len)){
k++;
}
int ans;
if(dp[L][k]<dp[R-(1<<k)+1][k]){
ans=dp[L][k];
}
else{
ans=dp[R-(1<<k)+1][k];
}
return ans;
}
int main(){
int i;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&dp[i][0]);
}
printf("0\n");
ST();
for(i=2;i<=n;i++){
int l,r;
r=i-1;
l=i-m;
if(l<=0){
l=1;
}
printf("%d\n",RMQ(l,r));
}
return 0;
}
by cszmc2004 @ 2017-08-24 08:28:14
倍增是nlogn的
by cszmc2004 @ 2017-09-06 20:58:45
这题数据强度不小
by 青衫白叙 @ 2017-10-07 22:03:49
建议单调队列 + 二分
by 青石巷 @ 2017-10-17 20:40:38
@青衫白叙 不是纯单调队列就好了吗……为什么会有二分……
by 青衫白叙 @ 2017-10-17 20:42:39
@青石巷 因为要刷榜啊(逃)
by 青衫白叙 @ 2017-10-17 20:43:21
@青石巷 其实是可以二分插入位置的,可是复杂度会很玄学。。。