题解 P5097 【[USACO2004OPEN]Cave Cows 2 洞穴里的牛之二】

· · 题解

这种静态区间的查询问题，还是最小值，O(1) 查询，它就是

ST表

ST表的思想是类似于倍增的，即f[i][j] 表示从j这个点向右2^i 的区间的最小值

那么我们建表就可以像倍增一样直接求个min

建表nlogn 查询O(1)

有模板题，详见P3865 【模板】ST表

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
const int big=0x7fffffff;
using namespace std;
inline void read(int &x)
{
    x=0;char ch=getchar();int pd=1;
    while(ch<'0'||ch>'9'){if(ch=='-')pd=-pd;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=pd;
}
inline void write(const int &x)
{
    char ggg[10001];int s=0;int tmp=x;
    if(tmp==0){putchar('0');return;}
    if(tmp<0){tmp=-tmp;putchar('-');}
    while(tmp>0){ggg[s++]=tmp%10+'0';tmp/=10;}
    while(s>0){putchar(ggg[--s]);}
}

int n,q,f[22][25010];
inline int query(int l,int r)
{
    int k=log2(r-l+1);//注意+1防止RE
    return min(f[k][l],f[k][r-(1<<k)+1]);
}

int main()
{
    read(n);
    read(q);
    for(register int i=1;i<=n;++i)
    {
        read(f[0][i]);
    }

    //这里是建表的过程
    for(register int j=1;j<=20;++j)
    {
        for(register int i=1;i+(1<<(j-1))<=n;++i)
        {
            f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
        }
    }
    while(q--)
    {
        int l,r;
        read(l);
        read(r);
        write(query(l,r));
        puts("");
    }
    return 0;
}