题解 P2251 【质量检测】
team109
2019-08-09 18:14:47
Update:2019.8.10。更新图片$\color{#cecece}{\textsf{，增设水印专区。}}$
Update:2020.2.19。改错别字；由于洛谷Markdown的一些feature又有了改动，于是还得跟着改。
Update:2020.3.12。Markdown又炸了。并修$\LaTeX$
首先，[$\bold{\Large{\color{#3399dd}{\text{双倍经验警告}}}}$](https://www.luogu.org/problem/P1886)
（弱弱地说一句：尽管ST表不是P1886标算，但还是可以AC的）
$ $
然后，把那题代码搬过来：
```cpp
//前面的部分省略
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表配滚动数组这种奇怪搭配。大概是我太水了吧。
___
$ $
现在稍微改一下，得到本题代码：
```cpp
#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]`数组，是这样预处理的：
```cpp
lg2[1]=0;
for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
```
只是这里不用。(~~lg2==某谷2？~~[滑稽])
这样就预处理完了。
接下来讲查询：
查询闭区间(就是指两个端点都取的到的)l...r,是这样的：
这里就要用到`lg2`数组了。
```cpp
int query(int l,int r)
{
int len=lg2[r-l+1];
return min(st[len][l],st[len][r-(1<<len)+1]);
}
```
最后给出我的代码仓库里的代码：
```cpp
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{完}}$