Pagini recente » Cod sursa (job #742975) | Cod sursa (job #367644) | Cod sursa (job #125490) | Cod sursa (job #2503104) | Cod sursa (job #3295242)
#include <fstream>
#define NM 100005
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int rmq[20][NM],n,m,u[NM];
int main()
{
int n,i,j,k,y,w,x,z,lg;
fin >> n>>m;
u[1]=0;
for(i=2; i<=n; i++)
u[i]=u[i/2]+1;
for(int i = 1; i <= n; ++i)
fin >>rmq[0][i];
for(i = 1,lg=2; lg<=n; i++,lg=2*lg)
for(j = 1; j+ lg-1<=n;j++)
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+lg/2]);
for(int i = 1; i <= m; ++i)
{
fin >> x >> y;
z = y - x + 1;
k=u[z];
w=min(rmq[k][x],rmq[k][y-(1<<k)+1]);
fout<<w<< '\n';
}
return 0;
}