Codevs 2173 忠誠

http://codevs.cn/problem/2173/

ST表

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,a,b,minx;
int num[],d[][];
void init()
{
    for(int i=;i<=n;i++)
    d[i][]=num[i];
    for(int j=;(<<j)<=n;j++)
    for(int i=;i+(<<j)-<=n;i++)
    d[i][j]=min(d[i][j-],d[i+(<<(j-))][j-]);
}
int query(int l,int r)
{
    int k=;
    while((<<(k+))<=r-l+)
    k++;
    return min(d[l][k],d[r-(<<k)+][k]);
}
int main()
{
    memset(d,,sizeof(d));
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
    scanf("%d",&num[i]);
    init();
    for(int i=;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d ",query(a,b));
    }
    return ;
}