题解 P2251 【质量检测】

首先,双倍经验警告(戳我)

(尽管ST表不是P1886标算,但还是可以AC的)
$ $

然后,把那题代码搬过来:

//前面的部分省略
int st1[1000005],st2[1000005];
int main()
{
    int n=read(),k=read(),tmp=log2(k+0.1);
    for(int i=1;i<=n;i++)st1[i]=st2[i]=read();
    for(int i=1;i<=tmp;i++)
        {
            for(int j=1;j<=n-(1<<i)+1;j++)
            st1[j]=max(st1[j],st1[j+(1<<i-1)]),st2[j]=min(st2[j],st2[j+(1<<i-1)]);
        }
    for(int i=1;i<=n-k+1;i++)
        print(min(st2[i],st2[i+k-(1<<tmp)])),putchar(' ');
    putchar('\n');
    for(int i=1;i<=n-k+1;i++)
        print(max(st1[i],st1[i+k-(1<<tmp)])),putchar(' ');
}

$ $

注意不用滚动数组会MLE。或者把st1和st2和在一起,输出st1后再算st2,就不会MLE了。

$ $
$ $

话说我有点扯远了,现在讲的可是P2251啊。 不过还是平生第一次见到ST表配滚动数组这种奇怪搭配。大概是我太水了吧。


$ $
现在稍微改一下,得到本题代码:

#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<<1)+(x<<3)+ch-'0',ch=getchar();
    b&&(x=-x);
    return x;
}
inline void print(int x)
{
    if(!x){putchar('0');return;}
    register int cnt=0;
    char ch[12];
    (x&-2147483648)&&(putchar('-'),x=-x);
    while(x)ch[cnt++]=x%10+48,x/=10;
    while(cnt--)putchar(ch[cnt]);
}
int st[1000005];
int main()
{
    int n=read(),k=read(),tmp=log2(k+0.1);
    for(int i=1;i<=n;i++)st[i]=read();
    for(int i=1;i<=tmp;i++)
        for(int j=1;j<=n-(1<<i)+1;j++)//防止溢出
            st[j]=min(st[j],st[j+(1<<i-1)]);
    for(int i=1;i<=n-k+1;i++)
        print(min(st[i],st[i+k-(1<<tmp)])),putchar('\n');
}

不知道有没有发现一个小问题?
$\color{white}\text{一个优秀的OIer是会数数字的位数的。}$ [滑稽](我照搬的时候没看到这题n才1e5,导致空间巨大)


$ $
$ $
$ $

最后讲一下ST表本身。

ST表是用倍增的思路实现的。
ST表专门用于O(1)处理区间最值的询问。

ST表的定义:
st[i][j]表示 $\mathtt{a[j]}$ 到 $\mathtt{a[j+2^i-1]}$ 一共 $\mathtt{2^i}$ 个数的最值。
如图(因为画图3D不资瓷上下标,所以就把指数一律改成2和3,这两个是可以在字符表里找到的)。 404

这样,因为总共n个数,所以一维下标做到log2(n)就可以了,所以st数组的一维下标是 O(logn多一点点) 的,二位下标是 O(n多一点点) 的。空间复杂度O(nlogn)。

然后讲ST表的O(nlogn)预处理。
首先, $\mathtt{st[0][i]=a[i]}$ ,没有问题。
然后,有 $\mathtt{st[i][j]=min(st[i-1][j],st[i-1][j+2^{i-1}])}$ 。如图。注意图中字母l和数字1长得是不一样的。
404 一般的ST表还要预处理一个lg2[1...n]数组,是这样预处理的:

lg2[1]=0;
for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;

只是这里不用。(lg2==某谷2?[滑稽])
这样就预处理完了。

接下来讲查询:
查询闭区间(就是指两个端点都取的到的)l...r,是这样的:
404
这里就要用到lg2数组了。

int query(int l,int r)
{
    int len=lg2[r-l+1];
    return min(st[len][l],st[len][r-(1<<len)+1]);
}

最后给出我的代码仓库里的代码:

int a[SIZE_],st[SIZE_LOGN][SIZE_],lg2[SIZE_];//SIZE_和SIZE_LOGN是两个我自己定义的宏
void pre(int n)
{
    memset(lg2,0,sizeof lg2);
    for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
}
int qry1(int l,int r)
{
    int len=lg2[r-l+1];
    return max(st[len][l],st[len][r-(1<<len)+1]);
}
void work1(int n)
{
    memset(st,-256,sizeof st);
    for(int i=1;i<=n;i++)st[0][i]=a[i];
    for(int i=1;i<=SIZE_LOG;i++)
        for(int j=1;j<=n;j++)st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
int qry2(int l,int r)
{
    int len=lg2[r-l+1];
    return min(st[len][l],st[len][r-(1<<len)+1]);
}
void work2(int n)
{
    memset(st,255,sizeof st);
    for(int i=1;i<=n;i++)st[0][i]=a[i];
    for(int i=1;i<=SIZE_LOG;i++)
        for(int j=1;j<=n;j++)st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}

$\boxed{\text{完}}$

Update:2019.8.10。更新图片 $\color{white}{\text{增设水印专区。}}$


发表于 2019-08-09 18:14:47 in 题解