洛谷 P1816 忠诚

题目传送门

RMQ模板题,st表分分钟AC

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int m,n,f[100001][30],l,r;

int main() {
    memset(f,0x3ACf3f3f3f,sizeof(f));
    scanf("%d%d",&m,&n);
    for(int i = 1;i <= m; i++)
        scanf("%d",&f[i][0]);
    for(int j = 1;j <= 20; j++)
        for(int i = 1;i <= m; i++)
            if(i + (1 << j) - 1 <= m)
                f[i][j] = min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int i = 1;i <= n; i++) {
        scanf("%d%d",&l,&r);
        int k = log2(r - l + 1);
        printf("%d ",min(f[l][k],f[r-(1<<k)+1][k]));
    }
    
    return 0;
}