Pagini recente » Cod sursa (job #2201314) | Cod sursa (job #2289744) | Cod sursa (job #1896768) | Cod sursa (job #796618) | Cod sursa (job #302764)
Cod sursa(job #302764)
#include <stdio.h>
#include <vector>
#define MAXN 100010
#define LOGMAXN 20
using namespace std;
long int a[MAXN],m[MAXN][LOGMAXN],m1,n,i,j,lg[MAXN],x,y,diff,sh,l;
int main()
{
freopen("rmq.in","r",stdin);
freopen("rmq.out","w",stdout);
scanf("%d %d",&n,&m1);
for(i=1; i<=n; i++) scanf("%d",&a[i]);
for(i=1; i<=n; i++) m[i][0]=i;
lg[1]=0;
for(i=2; i<=n; i++) lg[i]=lg[i/2]+1;
for(j=1; 1<<j<=n; j++)
for(i=1; 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];
for(i=1; i<=m1; i++)
{
scanf("%d %d",&x,&y);
diff=y-x+1;
l=lg[diff];
sh=diff-(1<<l);
printf("%d\n",min(a[m[x][l]],a[m[x+sh][l]]));
}
return 0;
}