RMQ

2017-11-03

作用：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。
还可以求配上df序求lca

下面是模板

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define re register
int n,m,f[100010][20];
void rmq(){
	for(re int j=1;(1<<j)<=n;j++)
	    for(re int i=1;i+(1<<j)-1<=n;i++)
	        f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int find(int l,int r){
	int k=(int)(log2(r-l+1));
	return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(re int i=1;i<=n;i++)scanf("%d",&f[i][0]);
    rmq();
    while(m--){
    	int l,r;
    	scanf("%d%d",&l,&r);
    	printf("%d ",find(l,r));
	}
	return 0;
}