题解 P1816 【忠诚】

浅色调 · 2017-09-15 15:14:59 · 题解

典型的RMQ模板题，本人用了相对简单的ST表

用数组a[i，j]表示从第i个数起连续2^j个数中的最小值，则很容易得到状态转移方程

a[i][j]=min(a[i][j-1],a[i+2^(j-1)][j-1]);

我们只需要开始时对于a数组进行预处理(时间复杂度n*(logn))

注意：

先更新所有长度为a[i][0]即1个元素，然后通过2个1个元素的最值获得所有长度为a[i][1]即2个元素的最值，以此类推更新。

然后对于每一次查询(时间复杂度O(1));

若查询区间为(i，j)，易得区间长度为j-i+1，所以取k=log(j-i+1),则min(i,j)=min(a[i][k],a[j-(1<<k)+1][k]);

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100005][20],m,n;
inline int getint()                    //读入优化
{
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')f=1,x=getchar();
    while(x>='0'&&x<='9')
    {a=a*10+x-'0';x=getchar();}
    return f?-a:a;
}
void rmq_st(int n)                //预处理，st表
{
    for(int j=1;j<=20;j++)
    for(int i=1;i<=n;i++)           //思考为什么外循环j套i，而不是外循环i套j
    if(i+(1<<j)-1<=n)
    a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1]);   //原因在于每个区间更新都是由1个点开始慢慢增加区间范围
}
int main()
{
    m=getint();n=getint();
    for(int i=1;i<=m;i++)a[i][0]=getint();   //读入数据，对于每个点开始时最小值就是它本身
    rmq_st(m);
    while(n--)
    {
        int l=getint(),r=getint(),k=log2(r-l+1);
        printf("%d ",min(a[l][k],a[r-(1<<k)+1][k]));        //查询时注意思路 
    }
    return 0;
}