hyfhaha @ 2018-08-02 08:59:28

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int fmax_[310101][33],fmin_[310101][33],s,n,m,p,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",&s);
        fmax_[i][0]=s;
        fmin_[i][0]=s;
    }
    //O(nlogn)预处理    DP、倍增思想 
    for(int j=1;j<=(int)(log2(n));j++)                          //j表示区间长度为2^j 
    {
        for(int i=1;i<=n-(1<<j)+1;i++)                          //i表示区间开始点                      
        {
            fmax_[i][j]=max(fmax_[i][j-1],fmax_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
            fmin_[i][j]=min(fmin_[i][j-1],fmin_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
        }
    }
    //O(1)查询
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",min(fmin_[x][p],fmin_[y-(1<<p)+1][p]));
    }
    printf("\n");
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",max(fmax_[x][p],fmax_[y-(1<<p)+1][p]));
    }
    return 0;
}

by Lolierl @ 2018-08-02 09:03:00

@hyfhaha

参考数据范围

by 剑舞红颜笑 @ 2018-08-02 09:09:06

二维数组不够大吗

by longlongzhu123 @ 2018-08-02 09:16:01

STO -HYF- ORZ

by hyfhaha @ 2018-08-02 09:16:54

感谢大佬，可改了之后MLE了

#include<cstdio>
#include<cmath>
#include<vector>
#include<iostream>
using namespace std;
int fmax_[1000101][20],fmin_[1000101][20],s,n,m,p,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",&s);
        fmax_[i][0]=s;
        fmin_[i][0]=s;
    }
    //O(nlogn)预处理    DP、倍增思想 
    for(int j=1;j<=(int)(log2(n));j++)                          //j表示区间长度为2^j 
    {
        for(int i=1;i<=n-(1<<j)+1;i++)                          //i表示区间开始点                      
        {
            fmax_[i][j]=max(fmax_[i][j-1],fmax_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
            fmin_[i][j]=min(fmin_[i][j-1],fmin_[i+(1<<(j-1))][j-1]);        //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
        }
    }
    //O(1)查询
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",min(fmin_[x][p],fmin_[y-(1<<p)+1][p]));
    }
    printf("\n");
    for(int i=1;i<=n-m+1;i++) 
    {
        x=i;y=i+m-1;
        if(y-x+1<=0)
        p=0;
        else
        p=(int)(log2(y-x+1));
        printf("%d ",max(fmax_[x][p],fmax_[y-(1<<p)+1][p]));
    }
    return 0;
}

可以再帮帮忙吗？

by longlongzhu123 @ 2018-08-02 09:17:11

\large Shi_{Ni^{Shu^{Zu}Kai}Xiao}Le^{Ba}

by hyfhaha @ 2018-08-02 09:18:47

TLE了

by asd_a @ 2018-08-02 09:23:33

ST表过不了，用单调队列

by hyfhaha @ 2018-08-02 09:27:49

哦 好吧 谢谢大佬 @asd_a

by Anguei @ 2018-08-02 23:02:51

@hyfhaha 理论上说，开两个 1000000 \times 20 的 int 数组只会占用 38\text{MB}空间，怎么会 MLE 呢？

by CreeperK @ 2018-08-08 09:48:52

@hyfhaha 可以做的，我用一个数组重复利用，开了个O2就压线过了