#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <limits>
template<typename T>
class SparseTable {
private:
T **table;
int height;
long size;
std::vector<int> *logarithm;
void build_logarithm_floor(long n) {
logarithm = new std::vector<int>(n + 1);
for (long i = 0; i < n + 1; i++)
(*logarithm)[i] = floor(log2(i + 1));
}
public:
SparseTable(std::vector<T> &array) {
size = array.size();
build_logarithm_floor(size);
height = (*logarithm)[logarithm->size() - 1] + 1;
long memory_in_bytes = height*sizeof(T *);
memory_in_bytes += size*sizeof(T);
long adder = size;
for (int i = 1; i < height; i++) {
memory_in_bytes += (adder - (1 << (i - 1)))*sizeof(T);
adder -= (1 << (i - 1));
}
table = (T **)malloc(memory_in_bytes);
//printf("Table memory consumption is %ld bytes\n", memory_in_bytes);
//printf("plus %ld bytes on logarithm cache\n", logarithm->size()*sizeof(T));
table[0] = (T *)(table + height);
for (int i = 0; i < size; i++) {
table[0][i] = array[i];
}
adder = size;
for (int i = 1; i < height; i++) {
table[i] = table[i - 1] + adder;
for (int j = 0; j < adder - (1 << (i - 1)); j++) {
table[i][j] = std::min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
adder -= (1 << (i - 1));
}
}
~SparseTable() {
free(table);
delete logarithm;
}
T rmq(long i, long j) {
if (i == j) return table[0][i];
int k = (*logarithm)[j - i];
return std::min(table[k][i], table[k][j - (1 << k) + 1]);
}
};
template<typename T>
class IntervalTree {
private:
T *data;
long size;
const T INF = std::numeric_limits<T>::max() - 1;
public:
IntervalTree(std::vector<T> &array) {
long n = (1 << ((static_cast<int>(floor(log2(array.size() - 1))) + 1))) - 1;
data = new T[2*n + 1];
for (long i = n, len = n + array.size(); i < len; i++)
data[i] = array[i - n];
for (long i = n + array.size(); i < 2*n + 1; i++)
data[i] = INF;
for (long i = n - 1; i >= 0; i--)
data[i] = std::min(data[2*i + 1], data[2*i + 2]);
size = 2*n;
for (long i = 0; i < size; i++)
std::cout << data[i] << " ";
std::cout << std::endl;
}
T rmq(long l, long r) {
T ans = INF;
long n = size / 2;
l += n, r += n;
while (l <= r)
{
// если l - правый сын своего родителя,
// учитываем его фундаментальный отрезок
if (!(l & 1))
ans = std::min(ans, data[l]);
// если r - левый сын своего родителя,
// учитываем его фундаментальный отрезок
if ((r & 1))
ans = std::min(ans, data[r]);
// сдвигаем указатели на уровень выше
l = (l) / 2, r = (r - 2) / 2;
//std::cout << "ans: " << ans << std::endl;
}
return ans;
}
~IntervalTree() {
delete[] data;
}
};
void compute_tree(int *A, int *T, int n)
{
int st[n], i, k, top = -1;
//we start with an empty stack
//at step i we insert A[i] in the stack
for (i = 0; i < n; i++) {
//compute the position of the first element that is
//equal or smaller than A[i]
k = top;
while (k >= 0 && A[st[k]] > A[i])
k--;
//we modify the tree as explained above
if (k != -1)
T[i] = st[k];
if (k < top)
T[st[k + 1]] = i;
//we insert A[i] in the stack and remove
//any bigger elements
st[++k] = i;
top = k;
}
//the first element in the stack is the root of
//the tree, so it has no father
T[st[0]] = -1;
}
int main() {
int data[14] = {0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 2, 0, 2, 2};
std::vector<int> lcp = std::vector<int>(data, data + sizeof(data)/sizeof(int));
SparseTable<int> st = SparseTable<int>(lcp);
IntervalTree<int> it = IntervalTree<int>(lcp);
//int *tree_data = new int[14];
//compute_tree(data, tree_data, 14);
for (long i = 0; i < 14; i++) {
for (long j = i; j < 14; j++) {
printf("i = %ld, j = %ld, %d::%d\n", i, j, st.rmq(i, j), it.rmq(i, j));
}
}
//printf("\n");
//for (int i = 0; i < 14; i++)
// printf("%d ", tree_data[i]);
//printf("\n");
return 0;
}