#include "secret.h"
#include <vector>
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <cassert>
std::map<std::pair<int, int>, int> secret_map;
int mySecret(int X, int Y) {
if(X == -2) return Y;
if(Y == -2) return X;
if(X == -1 || Y == -1) {
return -1;
}
if(secret_map.find({X, Y}) != secret_map.end()) {
return secret_map[{X, Y}];
}
return secret_map[{X, Y}] = Secret(X, Y);
}
struct DisjointSparseTable {
int lg2;
std::vector<std::vector<int>> table;
DisjointSparseTable() {}
DisjointSparseTable(std::vector<int> a) {
{
const int n = a.size();
lg2 = 0;
while ((1 << lg2) < n) {
++lg2;
}
assert((1 << lg2) >= n);
}
const int n = (1 << lg2);
a.resize(n, -1);
table.resize(lg2 + 1, a);
for(int level = 1; level <= lg2; level++) {
const int segment_size = (1 << level);
for(int segment_start = 0; segment_start < n; segment_start += segment_size) {
const int segment_end = segment_start + segment_size - 1;
const int mid = segment_start + segment_size / 2 - 1;
// segmentul meu e impartit la jumate ca [segment_start, mid] si [mid + 1, segment_end]
for(int i = mid - 1; i >= segment_start; i--) {
table[level][i] = mySecret(table[level][i], table[level][i + 1]);
}
for(int i = mid + 2; i <= segment_end; i++) {
table[level][i] = mySecret(table[level][i - 1], table[level][i]);
}
}
}
}
int query(int st, int dr) {
if(st == dr) {
return table[0][st]; // evident doar un element
}
int diff = st ^ dr;
// daca st si dr au un mijloc intre ele pe nivelul k
// inseamna ca st <= segment_start + 2^(k - 1) - 1
// si dr >= segment_start + 2^(k - 1)
// segment_start la randul lui este divizibil cu 2^k
// segment_start = segment_size * i
// segment_start + 2^(k - 1) - 1 = segment_size * i + (segment_size / 2) - 1
// \--------> are k de 0 la final in binar
// ?????????[k de 0] + 1[k - 1 de 0] - 1 = ???????????0[k - 1 de 1]
// st <= ?????????0[k - 1 de 1]
// dr >= ?????????[k de 1]
// \-------> foarte important, aceste ??????? sunt acelasi prefix si pentru st si pentru dr
// st = [prefix]0[????]
// dr = [prefix]1[????]
// st ^ dr = [prefix]1[????] ^ [prefix]0[????] = [0 de |prefix| ori]1[?????]
// noi stim ca 1[?????] trebuie sa fie la fel de lung ca sufixul de k de 0
// deci daca stiu pozitia primului 1 in st ^ dr, stiu si k
int nivel = 32 - __builtin_clz(diff); // parte intreaga a log2(diff)
// std::cerr << "query: " << st << " " << dr << std::endl;
// std::cerr << "nivel: " << nivel << std::endl;
return mySecret(table[nivel][st], table[nivel][dr]);
}
} dst;
void Init(int N, int A[]) {
std::vector<int> v(N);
for(int i = 0; i < N; i++) {
v[i] = A[i];
}
dst = DisjointSparseTable(v);
}
int Query(int L, int R) {
return dst.query(L, R);
}
