Pagini recente » Cod sursa (job #1129734) | Istoria paginii runda/runda1 | Cod sursa (job #2378346) | Cod sursa (job #2182865) | Cod sursa (job #2789142)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int n, m, a[100005], rmq[100005][18], lg[100005];
int query(int st, int dr)
{
int k = lg[dr - st + 1];
return min(rmq[st][k], rmq[dr - (1 << k) + 1][k]);
}
void solve()
{
fin >> n >> m;
lg[1] = 0;
for(int i = 2; i <= n; i ++)
{
lg[i] = lg[i/2] + 1;
}
for(int i = 1; i <= n; i ++)
{
fin >> a[i];
rmq[i][0] = a[i];
}
for(int k = 1; k < 18; k ++)
{
for(int i = 1; i + (1 << k) - 1 <= n ; i ++)
rmq[i][k] = min(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
}
for(int i = 1; i <= m; i ++)
{
int st, dr;
fin >> st >> dr;
fout << query(st, dr) << '\n';
}
}
int main()
{
solve();
return 0;
}