Pagini recente » Cod sursa (job #1724660) | Cod sursa (job #1442801)
#include <fstream>
#include <cstring>
#include <deque>
using namespace std;
static const int MAXN = 100009;
static const int INF = 0x3F3F3F3F;
static const int LG = 18;
int n, m;
int v[LG][MAXN];
int main()
{
int x, y;
ifstream f("rmq.in");
ofstream g("rmq.out");
f >> n >> m;
for(int i = 1; i <= n; i++)
{
f >> v[0][i];
}
for(int i = 1; i < LG; i++)
{
for(int j = 1; j <= n; j++)
{
v[i][j] = min(v[i - 1][j], v[i - 1][min(n, (j + (1 << (i - 1))))]);
}
}
for(int i = 0; i < m; i++)
{
f >> x >> y;
int ans = INF;
for(int j = LG - 1; j >= 0; j--)
{
if(x + (1 << j) - 1 <= y)
{
ans = min(ans, v[j][x]);
x += (1 << j);
}
}
g << ans << '\n';
}
f.close();
g.close();
return 0;
}