Pagini recente » Cod sursa (job #356157) | Cod sursa (job #3170437) | Cod sursa (job #2778151) | Cod sursa (job #3032692) | Cod sursa (job #373497)
Cod sursa(job #373497)
using namespace std;
#include <cstdio>
#define MAX 100010
int a[MAX], n, M[20][MAX] ;
int Query(int i,int j){
int k=0,p=1;
while(p<j-i+1)
p<<=1, k++;
if(p>j-i+1)
k--;
if(a[M[i][k]] <= a[M[j-(1<<k)+1][k]])
return a[M[i][k]];
else
return a[M[j-(1<<k)+1][k]];
}
void Process(){
for(int i=1;i<n;i++)
M[i][0] = i;
for(int j = 1 ; 1<<j <= n ; ++j)
for(int i = 0; i+ (1<<j)-1<n ; ++i)
if( a[M[i][j-1]] < a[M[i+1<<(j-1)][j-1]])
M[i][j] = M[i][j-1];
else
M[i][j] = M[i+1<<(j-1)][j-1];
}
int main(){
freopen("rmq.in", "r", stdin);
int m,i,j;
scanf("%d%d", &n,&m);
for(i=0;i<n;++i)
scanf("%d",a+i);
Process();
freopen("rmq.out","w",stdout);
for( ; m ; --m){
scanf("%d%d", &i , &j);
printf("%d\n", Query(i-1,j-1));
}
return 0;
}