Pagini recente » Cod sursa (job #1729103) | Cod sursa (job #2188198) | Cod sursa (job #1918595) | Cod sursa (job #1899836) | Cod sursa (job #1501682)
#include<fstream>
#define DIM 100005
using namespace std;
ifstream fin ("rmq.in");
ofstream fout("rmq.out");
int D[17][DIM],P[DIM],n,m,i,k,p,a,b;
int main(){
fin>>n>>m;
for(i=1;i<=n;i++){
fin>>D[0][i];
}
//D[k][i]=min(D[k-1][i],D[k-1][i+2^k-1];
for(k=1;(1<<k)<=n;k++){
for(i=1;i<=n;i++){
D[k][i]=D[k-1][i];
if(i+(1<<k-1)<=n){
D[k][i]=min(D[k][i],D[k-1][i+(1<<k-1)]);
}
}
}
P[1]=1;
p=1;
for(i=2;i<=n;i++){
if(p*2==i){
P[i]=1;
p*=2;
}
}
for(i=1;i<=m;i++){
fin>>a>>b;
p=P[b-a+1];
fout<<min(D[p][a],D[p][b-(1<<p)+1])<<"\n";
}
return 0;
}