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{完}}$