Pagini recente » Cod sursa (job #1967467) | Borderou de evaluare (job #1791708) | Cod sursa (job #979563) | Borderou de evaluare (job #2016238) | Cod sursa (job #2306195)
#include<stdio.h>
#define N(x,y) (a[x]<a[y]?x:y)
int n,m,a[100001],i,j,b[100001][18],k,x,y;
int main()
{
freopen("rmq.in","r",stdin),freopen("rmq.out","w",stdout),scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&a[i]),b[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
b[i][j]=N(b[i][j-1],b[i+(1<<(j-1))][j-1]);
while(m--)
{
scanf("%d%d",&x,&y),x--,y--;
for(k=1;(1<<k)<=y-x+1;k++);
k--,printf("%d\n",a[N(b[x][k],b[y-(1<<k)+1][k])]);
}
}