Pagini recente » Cod sursa (job #1001519) | Cod sursa (job #1112645) | Cod sursa (job #2180932) | Cod sursa (job #1888879) | Cod sursa (job #3041539)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
#define cin fin
#define cout fout
ifstream fin ("rmq.in");
ofstream fout ("rmq.out");
const int LGMAX=21;
const int NMAX=1e5+5;
int rmq[LGMAX][NMAX];
int lg[NMAX];
int v[NMAX];
int query(int x,int y)
{
int interv=y-x+1;
int l=lg[interv];
return min(rmq[l][x],rmq[l][x+interv-(1<<l)]);
}
int main()
{
int n,m,i,j,e;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>v[i];
rmq[0][i]=v[i];
}
lg[1]=0;
for(i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for(e=1;(1<<e)<=n;e++)
for(i=1;i<=n;i++)
{
if(i+(1<<(e-1))>n)
continue;
rmq[e][i]=min(rmq[e-1][i],rmq[e-1][i+(1<<(e-1))]);
}
for(i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
cout<<query(x,y)<<"\n";
}
return 0;
}