Cod sursa(job #520192)

Utilizator coderninuHasna Robert coderninu Data 7 ianuarie 2011 14:51:40
Problema Range minimum query Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <vector>

using namespace std;

int N, M, L;
vector< int > v;
vector< vector< int > > RMQ;

inline int min(int x, int y) { return x < y ? x : y; }

int getLog(int x) {
    int rez = 0;
    while ((1 << rez) < x) ++rez;
    return rez;
}

void compute() {
    L = getLog(N);
    RMQ.assign(N, vector<int>(L, 0));
    for (int i = 0; i < N; ++i) 
        RMQ[i][0] = i;

    for (int l = 1; l < L; ++l)
        for (int i = 0; i + (1 << l) <= N; ++i)
            if (v[ RMQ[i][l-1]] < v[ RMQ[ i + (1 << (l-1)) ][l-1]])
                RMQ[i][l] = RMQ[i][l-1];
            else
                RMQ[i][l] = RMQ[i + (1 << (l-1))][l-1];
}

int query(int a, int b) {
    int L = getLog(b - a + 1) - 1;
    return min(v[RMQ[a][L]], v[RMQ[b - (1 << L) + 1][L]]);
}

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

    scanf("%d %d\n", &N, &M);
    v.reserve(N);

    for (int i = 0; i < N; ++i) {
        int tmp;
        scanf("%d\n", &tmp);
        v.push_back(tmp);
    }

    compute();
    
    while (M--) {
        int a, b;
        scanf("%d %d\n", &a, &b);
        printf("%d\n", query(a-1,b-1) );
    }

    return 0;
}