#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
SparseTable* temp;
vector<int> array2;
class SparseTable{
private:
vector<vector<int>> table;
vector<int> arr;
int sze;
int logSze;
void build(int depth, int left, int right){
if(depth==right){
return;
}
else{
int mid = (left+right)/2;
table[depth][mid]=arr[mid];
for(int i=mid-1; i>=left; i--){
table[depth][i]=Secret(table[depth][i+1], arr[i]);
}
table[depth][mid+1]=arr[mid+1];
for(int i=mid+2; i<=right; i++){
table[depth][i]=Secret(table[depth][i-1], arr[i]);
}
build(depth+1, left, mid);
build(depth+1, mid+1, right);
}
}
int privQuery(int depth, int queryLeft, int queryRight, int posLeft, int posRight){
if(queryLeft>posRight || queryRight<=posLeft){
return 0;
}
int mid = (posLeft+posRight)/2;
if(queryRight==mid){
return table[depth][queryLeft];
}
else if(queryLeft==mid+1){
return table[depth][queryRight];
}
else{
if(queryLeft<=mid && queryRight>=mid+1){
return Secret(table[depth][queryLeft], table[depth][queryRight]);
}
else{
if(queryLeft>=mid+1){
return privQuery(depth+1, queryLeft, queryRight, mid+1, posRight);
}
else{
return privQuery(depth+1, queryLeft, queryRight, posLeft, mid);
}
}
}
}
public:
SparseTable(vector<int>& vect){
sze = vect.size();
logSze = ceil(log2(sze))+1;
arr.resize(sze);
for(int i=0; i<(int) vect.size(); i++){
arr[i]=vect[i];
}
table.resize(logSze, vector<int>(sze));
build(0, 0, sze-1);
}
int query(int left, int right){
return privQuery(0, left, right, 0, sze-1);
}
};
void Init(int N, int A[]) {
vector<int> vect(N);
array2.resize(vect.size());
for(int i=0; i<N; i++){
vect[i]=A[i];
array2[i]=A[i];
}
temp = new SparseTable(vect);
}
int Query(int L, int R) {
if (L == R) return array2[L];
return temp->Query(L, R);
}
Compilation message
secret.cpp:5:1: error: 'SparseTable' does not name a type
5 | SparseTable* temp;
| ^~~~~~~~~~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:80:2: error: 'temp' was not declared in this scope
80 | temp = new SparseTable(vect);
| ^~~~
secret.cpp: In function 'int Query(int, int)':
secret.cpp:85:9: error: 'temp' was not declared in this scope
85 | return temp->Query(L, R);
| ^~~~
