Pagini recente » Cod sursa (job #3156710) | Cod sursa (job #3283823) | Cod sursa (job #2987393) | Cod sursa (job #2590369) | Cod sursa (job #2748669)
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN=100001,Log2Max=17;
int v[MaxN],mn[Log2Max][MaxN],lg2[MaxN];
int main() {
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int n,q,x,y,lg;
fin>>n>>q;
for(int i=1;i<=n;i+=1)
fin>>v[i];
for(int i=3;i<=n;i+=1)
lg2[i]=lg2[i>>1]+1;
for(int i=1;i<=n;i+=1)
mn[0][i]=v[i];
for(int p=1;p<=Log2Max;p+=1)
for(int i=1;i+(1<<p)-1<=n;i+=1)
mn[p][i]=min(mn[p-1][i],mn[p-1][i+(1<<(p-1))]);
while(q--) {
fin>>x>>y;
lg=lg2[y-x+1];
fout<<min(mn[lg][x],mn[lg][y-(1<<lg)+1])<<"\n";
}
return 0;
}