# Cod sursa(job #1999292)

Utilizator Data 10 iulie 2017 20:14:30 Range minimum query 100 cpp done Arhiva educationala 1.87 kb
``````#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

template<typename T, class cmp = less<T> >
class RMQ {

private:

int n;
vector< vector<T> > rmqTable;
vector<int> logarithm;

T best(T a, T b) {

if (cmp()(a, b))
return a;
else
return b;
}

public:

RMQ(){}

RMQ(const vector<T>& v) {

this->n = v.size();

logarithm.resize(n + 1);

for (int i = 2; i <= n; ++i)
logarithm[i] = logarithm[i >> 1] + 1;

rmqTable.resize(logarithm[n] + 1);

rmqTable[0].resize(n);
rmqTable[0] = v;
}

void build() {

for (int k = 1; (1 << k) <= n; ++k) {

int len = (1 << (k - 1));

for (int i = 0; i + len - 1 < n; ++i) {
rmqTable[k].push_back(0);
rmqTable[k][i] = best(rmqTable[k - 1][i], rmqTable[k - 1][i + len]);
}
}
}

T query(int left, int right) {

assert(left >= 0 && right < n && left <= right);

int lg = logarithm[right - left + 1];

return best(rmqTable[lg][left], rmqTable[lg][right - (1 << lg) + 1]);
}
};

int main() {

ifstream fin("rmq.in");
ofstream fout("rmq.out");

int N, Q;

vector<int> v;

fin >> N >> Q;

v.resize(N);

for (int i = 0; i < N; ++i)
fin >> v[i];

/* How to declare: */
RMQ<int> myRMQ(v);

/* How to use: */

/* Step 1: build the table */
myRMQ.build();

/* Step 2: answer queries */

while (Q--) {
int x, y;

fin >> x >> y;

fout << myRMQ.query(x - 1, y - 1) << "\n";
}
/*
cout << myRMQ.query(1, 3) << "\n";
cout << myRMQ.query(0, 2) << "\n";
*/
return 0;
}
``````