# Cod sursa(job #154199)

Utilizator Data 10 martie 2008 23:21:28 Range minimum query 100 cpp done Arhiva educationala 1.39 kb
``````#include <cstdio>
#include <vector>
#include <math.h>

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector< vi > vii;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int, int> ii;
#define PB push_back
#define SZ(v) v.size()
#define ALL(v) (v).begin(), (v).end()
#define FORIT(i,c) for (typeof((c).end()) i=(c).begin(); i!=(c).end(); ++i)
#define FOR(i,n) for (int i = 0; i<(n); ++i)
#define FORE(i,n) for (int i = 0; i<=(n); ++i)
#define FORI(i,n1,n2) for (int i = n1; i<(n2); ++i)
#define FORIE(i,n1,n2) for (int i = n1; i<=(n2); ++i)
#define FORV(i,v) for (unsigned int i = 0; i<SZ(v); ++i)

#define INF 0x3f3f3f3f
#define EPS 1e-9

#define NMAX 100000
#define LOGMAX 20

int N,M;
int A[LOGMAX][NMAX];
int lg[NMAX];

int main()
{
freopen("rmq.in", "r", stdin);
freopen("rmq.out", "w", stdout);

scanf("%d %d", &N, &M);

FOR(i,N)
scanf("%d", &A[0][i]);

for (int i = 1, k = 2, kp2 = 1; k<=N; ++i, kp2 = k, k<<=1)
{
for (int j = 0; j<=N-k; ++j)
A[i][j] = min(A[i-1][j], A[i-1][j+kp2]);
}

FORIE(i,1,N)
lg[i] = (int)log2(i);

FOR(i,M)
{
int st, dr;
scanf("%d %d", &st, &dr); --st; --dr;
int dist = dr-st+1;
int k = lg[dist];
printf("%d\n", min(A[k][st], A[k][dr-(1<<k)+1]));
}

return 0;
}
``````