#题解##P1816 忠诚#

静态区间查找最值使用st算法

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int a[N],dpmin[N][21];
void stint()
{
    for(int i=1;i<=n;i++)//初始化
    {
        dpmin[i][0]=a[i];
    }
    int p=(int)(log(double(n))/log(2.0));
    for(int k=1;k<=p;k++)//处理
    {
        for(int s=1;s+(1<<k)<=n+1;s++)
        {
            dpmin[s][k]=min(dpmin[s][k-1],dpmin[s+(1<<(k-1))][k-1]);
        }
    }
}
int stq(int l,int r)//查询
{
    int k=log2(r-l+1);
    return min(dpmin[l][k],dpmin[r-(1<<k)+1][k]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    stint();
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        cout<<stq(l,r)<<" ";
    }
}