ST表MLE求救

team109 @ 2019-07-31 20:58:16

by 糖hhhh？ @ 2019-07-31 21:05:10

我的数组开了4个4百万都没事

by presucc @ 2019-07-31 21:05:47

128MB 不是能开3.2*10^7个int吗

by ud2_ @ 2019-07-31 21:13:30

> 18 * 1000005 * 2 * 4 / 1024 / 1024
< 137.3297882080078

by team109 @ 2019-07-31 21:16:35

@wthhhhhhh @LZCR 可我是36个一百万啊

by team109 @ 2019-07-31 21:16:54

详见代码

by presucc @ 2019-07-31 21:19:24

@team109

您可以用一个st数组来做。只开一个st数组，先跑一遍最大值，用一个1000000的数组记录下来，然后清空这个st数组，再跑一遍最小值，然后输出两个数组。

理论上空间可以变成原来的0.5倍的。

不过我没试过

by team109 @ 2019-07-31 21:22:44

@LZCR 谢谢。

by team109 @ 2019-07-31 21:54:22

@LZCR 不对呀，WA了

by presucc @ 2019-07-31 22:18:15

@team109

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register char ch=getchar();
    register int x=0;
    register bool b=0; 
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    (ch=='-')&&(b=1,ch=getchar());
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    if(b)return -x;
    return x;
}
void print2(int x)
{
    if(x>9)print2(x/10);
    putchar(x%10+48);
}
void print(int x)
{
    if(x<0)putchar('-'),print2(-x);
    else print2(x);
}
int q[1200000],ans1[1200000],ans2[1200000];
int st1[20][1200000];
int main()
{
    int n=read(),k=read(),tmp=log2(k+0.1);
//  for(int i=1;i<=n;i++)st1[0][i]=st2[0][i]=read();
    for(int i=1;i<=n;i++)q[i]=read();
    for(int i=1;i<=n;i++)st1[0][i]=q[i];
    for(int i=1;i<=tmp;i++)
        for(int j=1;j<=n-(1<<i)+1;j++)
            st1[i][j]=max(st1[i-1][j],st1[i-1][j+(1<<i-1)]);
    for(int i=1;i<=n-k+1;i++)
        ans1[i]=(max(st1[tmp][i],st1[tmp][i+k-(1<<tmp)]));

    memset(st1,0,sizeof(st1));
    for(int i=1;i<=n;i++)st1[0][i]=q[i];
    for(int i=1;i<=tmp;i++)
        for(int j=1;j<=n-(1<<i)+1;j++)
            st1[i][j]=min(st1[i-1][j],st1[i-1][j+(1<<i-1)]);
    for(int i=1;i<=n-k+1;i++)
        ans2[i]=(min(st1[tmp][i],st1[tmp][i+k-(1<<tmp)]));
    for(int i=1;i<=n-k+1;i++) print(ans2[i]),putchar(' ');
    printf("\n");
    for(int i=1;i<=n-k+1;i++) print(ans1[i]),putchar(' ');  

//  putchar('\n');
//  for(int i=1;i<=n-k+1;i++)
//      print(max(st1[tmp][i],st1[tmp][i+k-(1<<tmp)])),putchar(' ');
}

by presucc @ 2019-07-31 22:18:41

@team109

稍微改了一下，用两个数组记录答案，A了