Update:2019.8.10。更新图片$\color{#cecece}{\textsf{,增设水印专区。}}$
Update:2020.2.19。改错别字;由于洛谷Markdown的一些feature又有了改动,于是还得跟着改。
Update:2020.3.12。Markdown又炸了。并修$\LaTeX$
首先,$\bold{\Large{\color{#3399dd}{\text{双倍经验警告}}}}$
(弱弱地说一句:尽管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[100005];
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');
}
$ $
最后讲一下ST表本身。
ST表是用倍增的思路实现的。
ST表专门用于O(1)处理区间最值的询问。
ST表的定义:
st[i][j]
表示$\mathtt{a[j]}$到$\mathtt{a[j+2^i-1]}$一共$\mathtt{2^i}$个数的最值。
如图(因为画图3D不资瓷上下标,所以就把指数一律改成2和3,这两个是可以在字符表里找到的)。
这样,因为总共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
长得是不一样的。
一般的ST表还要预处理一个
lg2[1...n]
数组,是这样预处理的:
lg2[1]=0;
for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
只是这里不用。(lg2==某谷2?[滑稽])
这样就预处理完了。
接下来讲查询:
查询闭区间(就是指两个端点都取的到的)l...r,是这样的:
这里就要用到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{\textbf{完}}$