111l @ 2019-02-21 13:37:56
第二个点913msQAQ
#include<cstdio>
#include<cstring>
int n,m,a[2111111];
int c[2111111];
inline int min(int a,int b){return a<b?a:b;}
inline int lowbit(int x){return x&-x;}
void build(int x){
for(int i=1;i<=x;i++){
c[i]=a[i];
int t=lowbit(i);
for(int j=1;j<t;j<<=1){
c[i]=min(c[i],c[i-j]);
}
}
}
int getmin(int l,int r){
int res=1061109567;
int i=r;
while(i>=l){
int j=i-lowbit(i)+1;
if(j>=l){
res=min(res,c[i]);
i=j-1;
}
else{
res=min(res,a[i]);
--i;
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;scanf("%d",&a[i]),i++);
build(n);
for(int i=1;i<=n;i++){
int l=i-m,r=i-1;
if(l<=0) l=1;
if(l>r) puts("0");
else printf("%d\n",getmin(l,r));
}
}
by ニヒル @ 2019-02-21 13:45:29
@大湿 加下快读?
by 111l @ 2019-02-21 13:45:44
@ニヒル 我试试
by 111l @ 2019-02-21 13:50:35
@ニヒル 依然TLE只不过第二个点变成了700+ms是不是我太弱了
by Juanzhang @ 2019-02-21 13:51:36
@大湿 树状数组时间复杂度不对啊、、
by ニヒル @ 2019-02-21 13:52:59
@大湿 要么再register一下变量之类的吧,再过不了还是推荐写O(n)做法了qwq
by 111l @ 2019-02-21 13:54:33
%%% 各位大佬,我还是放弃树状数组吧
by AC_Automation @ 2019-02-21 14:04:53
单调队列大法好啊