记录编号	269647	评测结果	AAAAAAAAAA
题目名称	忠诚	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.743 s
提交时间	2016-06-13 20:16:27	内存使用	16.77 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=200100;
void RMQ_init(const int*,int);
int RMQ_min(int,int);
//int RMQ_max(int,int);
int n,m,mn[maxn][30]/*,mx[maxn][30]*/,a[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("faithful.in","r",stdin);
	freopen("faithful.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	RMQ_init(a,n);
	for(int i=0,l,r;i<m;i++){
		scanf("%d%d",&l,&r);
		if(i)printf(" ");
		printf("%d",RMQ_min(l,r));
	}
	return 0;
}
void RMQ_init(const int* a,int n){
	for(int i=1;i<=n;i++)mn[i][0]/*=mx[i][0]*/=a[i];
	for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++){
		mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		//mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
	}
}
int RMQ_min(int l,int r){
	int k=(int)log2(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
/*int RMQ_max(int l,int r){
	int k=(int)log2(r-l+1);
	return max(mx[l][k],mx[r-(1<<k)+1][k]);
}*/