倍增ST为啥全RE只有20分？？？

Ruff @ 2018-09-07 21:07:15

by jiangby @ 2018-09-07 21:10:39

不发代码怎么知道啊

by Ruff @ 2018-09-07 21:15:12

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200005
using namespace std;
int n,m;
int a[maxn];
int f[maxn*2][26*2];
int lg2[maxn*2];
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=l*10+ch-'0';
        ch=getchar();
    }
    return l*w;
}
void init()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    a[i]=read(),f[i][0]=a[i];
    for(int i=2;i<=n;i++)
    lg2[i]=lg2[i>>1]+1;
    for(int j=1;j<=26;j++)
        for(int i=1;i+(1<<(j-1))<=n;i++)
        f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int ST(int l,int r)
{
    int t=lg2[r-l+1];
    return min(f[l][t],f[r+1-(1<<t)][t]);
}
void work()
{
    printf("0\n");
    for(int i=2;i<=m;i++)
    printf("%d\n",ST(1,i-1));
    for(int i=m+1;i<=n;i++)
    printf("%d\n",ST(i-m,i-1));
}
int main()
{
    init();
    work();
    return 0;
}