树状数组90分求助,TLE一个点

P1440 求m区间内的最小值

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

单调队列大法好啊


|