#include "secret.h"
#include <vector>
template<class T, int SZ> offlineDQ {
int n;
T stor[SZ][32-__builtin_clz(SZ)], id = 1;
vector<T> a;
T comb (T a, T b) { return Secret(a, b); } // associative operation
void fill(int l, int r, int ind) {
if (ind < 0) return;
int m = (l+r)/2;
T prod = id; ROF(i,l,m) stor[i][ind] = prod = comb(a[i],prod);
prod = id; FOR(i,m,r) stor[i][ind] = prod = comb(prod,a[i]);
fill(l,m,ind-1); fill(m,r,ind-1);
}
void init(int N) {
n = 1; while ((1<<n) < sz(a)) ++n;
a.rsz(1<<n); fill(0,(1<<n),n-1);
}
T query(int l, int r) {
if (l == r) return a[l];
int t = 31-__builtin_clz(r^l);
return comb(stor[l][t],stor[r][t]);
}
}
void Init(int N, int A[]) {
offlineDQ<int, N> odq;
odq.a.resize(N);
for(int i = 0; i < N; i++) odq.a[i] = A[i];
odq.init();
}
int Query(int L, int R) {
return odq.query(--L, --R);
}
Compilation message
secret.cpp:4:27: error: 'offlineDQ' does not name a type
4 | template<class T, int SZ> offlineDQ {
| ^~~~~~~~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:28:3: error: 'offlineDQ' was not declared in this scope
28 | offlineDQ<int, N> odq;
| ^~~~~~~~~
secret.cpp:28:13: error: expected primary-expression before 'int'
28 | offlineDQ<int, N> odq;
| ^~~
secret.cpp:29:3: error: 'odq' was not declared in this scope
29 | odq.a.resize(N);
| ^~~
secret.cpp: In function 'int Query(int, int)':
secret.cpp:35:10: error: 'odq' was not declared in this scope
35 | return odq.query(--L, --R);
| ^~~
