ST表求助，MLE*2

紫妹只有17岁 @ 2018-09-01 20:14:47

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int N=2000001;
const int LogN=21;
int n,m;
int a[N],f[N][LogN+5],LOG[LogN+5];
void slove()
{
    int k=log(n)/log(2)+1;
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n-LOG[j-1];i++)
            f[i][j]=min(f[i][j-1],f[i+LOG[j-1]][j-1]);
    return ;
}
int find(int l,int r)
{
    int k=log(r-l+1)/log(2);
    return min(f[l][k],f[r-LOG[k]+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    LOG[0]=1;
    for(int i=1;i<=LogN;i++)
    LOG[i]=LOG[i-1]<<1;
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),f[i][0]=a[i];
    slove();
    int s=1;
    cout<<0<<endl;
    while(s<=m)
    {
        printf("%d\n",find(1,s));
        s++;
    }
    for(int i=m+1;i<=n-1;i++)
    {
        printf("%d\n",find(i-m+1,i));
    }
    return 0;
}

by 紫妹只有17岁 @ 2018-09-01 20:35:57

WOC我ST过了！！！…………

谢谢楼上各位dalao的帮助

by zhaotiensn @ 2018-09-01 20:39:30

@紫妹只有17岁 好奇怎么过的啊？

by zhaotiensn @ 2018-09-01 20:52:37

@UKE自动机

请当我刚才没有说过。。

滚存了一下。。

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int N=2000001;
const int LogN=21;
int n,m,k;
int a[N],f[N][2],LOG[LogN+5];
void slove()
{
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n-LOG[j-1];i++)
            f[i][j&1]=min(f[i][(j+1)&1],f[i+LOG[j-1]][(j+1)&1]);
    return ;
}
int find(int l,int r)
{
    int k=log(r-l+1)/log(2);
    return min(f[l][k],f[r-LOG[k]+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    LOG[0]=1;
    k=log(m)/log(2);
    for(int i=1;i<=LogN;i++)
    LOG[i]=LOG[i-1]<<1;
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),f[i][0]=a[i];
    slove();
    int minn=a[1];
    puts("0");
    for(int i=2;i<=m;i++){
        printf("%d\n",minn);
        minn=min(a[i],minn);
    }
    for(int i=m+1;i<=n;i++){
        printf("%d\n",min(f[i-m][k&1],f[i-LOG[k]][k&1]));
    }
    return 0;
}

by enceladus @ 2018-09-26 19:03:05

@紫妹只有17岁 你ST表是怎么过的，求教。 我的代码

#include<cmath>
#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
int n,m,a[2000001][23];
int x,y; 

inline void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline int Min(R int a,R int b)
{
    if(a>b) return b;
    else return a;
}
inline int query(R int x,R int y){
    int l=log(y-x+1)/log(2);
    return Min(a[x][l],a[y-(1<<l)+1][l]); 
}

int main()
{
    read(n);read(m);
    for(R int i=1;i<=n;i++){
        read(a[i][0]);
    }   
    for(R int j=1;j<=22;j++)
        for(R int i=1;i+(1<<j)-1<=n;i++){
            a[i][j]=Min(a[i][j-1],a[i+(1<<(j-1))][j-1]);
        }
    for(R int i=1;i<=n;i++){
        if(i==1){
            print(0);
            printf("\n");
        }
        else if(i<=m){
            print(query(1,i-1));
            printf("\n");
        }
        else if(i>m){
            print(query(i-m,i-1));
            printf("\n");
        }
    }
    return 0;
}