Pagini recente » Cod sursa (job #1093946) | Cod sursa (job #1724976) | Monitorul de evaluare | Cod sursa (job #1469745) | Cod sursa (job #3255514)
#include <fstream>
using namespace std;
ifstream cin("rmq.in");
ofstream cout("rmq.out");
int n,q,x,y,a[20][100001],p[100001];
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[0][i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j];
if((1<<(i-1))+j<=n)
a[i][j]=min(a[i][j],a[i-1][(1<<(i-1))+j]);
}
for(int i=2;i<=n;i++)
p[i]=p[i/2]+1;
while(q--){
cin>>x>>y;
int exp=p[y-x+1];
cout<<min(a[exp][x],a[exp][y-(1<<exp)+1])<<'\n';
}
return 0;
}