rmq模板题。用st表切一个。
关于st表的详解见我的博客：三种数据结构处理RMQ问题 笔记与思路整理
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入格式
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式
输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入 #110 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10输出 #12 3 1
裸rmq。M长度的数组，N次请求，给出左右端点求最小值。
#include <bits/stdc++.h> using namespace std; int stmin[100010][20]; int M, N, arr[100010]; void init(){ for(int j = 1 ; j <= M ; j++) stmin[j][0]=arr[j]; for(int i = 1 ; i <= log2(M) ; i++){ for(int j = 1 ; j <= M ; j++){ stmin[j][i] = stmin[j][i-1]; if(j + (1 << (i-1)) <= M ) stmin[j][i] = min(stmin[j][i], stmin[j+(1<<(i-1))][i-1]); } } } int query(int l,int r){ int len = log2(r - l + 1); return min(stmin[l][len],stmin[r - (1 << len) + 1][len]); } int main(){ scanf("%d %d", &M, &N); for(int i = 1 ; i <= M ; i++) scanf("%d", &arr[i]); init(); int l, r; for(int i = 1 ; i <= N ; i++ ){ scanf("%d %d", &l, &r); printf("%d ", query(l, r)); } return 0; }
原文：https://www.cnblogs.com/miserweyte/p/11477752.html