ST表挂了,优化前3个TLE,优化完2个MLE qwq

P1440 求m区间内的最小值

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 去看看题解吧有写


|