#include "secret.h" #include <bits//stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll int #define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1)) #define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1)) #define pll pair<ll, ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 ll n, ht[20][1025], a[1025], bn; ll lg; void build(ll s, ll e, ll layer) { if (e - s == 1) return; ll m = ((s + e)>>1); m--; ht[layer][m] = a[m]; //cout << s << " " << e << " " << m << endl; iloop(m-1, s-1) { if (a[i] != -1) ht[layer][i] = Secret(a[i], ht[layer][i+1]); //cout << i << " " << a[i] << " " << ht[layer][i+1] << " " << ht[layer][i] << "," << endl; } if (m + 1 < e) { ht[layer][m+1] = a[m+1]; iloop(m+2, e) { if (a[i] != -1) ht[layer][i] = Secret(ht[layer][i-1], a[i]); } } m++; if (e - s > 1) { build(s, m, layer + 1); build(m, e, layer + 1); } } void Init(int N, int A[]) { memset(ht, 0, sizeof(ht)); memset(a, -1, sizeof(a)); n = N; lg = 31 - __builtin_clz(n); if (n == 1<<lg) { bn = n; } else { lg++; bn = 1<<lg; } iloop(0, n) a[i] = A[i]; build(0, bn, 0); /*iloop(0, lg) { jloop(0, bn) cout << ht[i][j] << " "; cout << endl; }*/ } int Query(int L, int R) { if (L == R) return a[L]; ll h = 31 - __builtin_clz(L^R); ll lay = lg - 1 - h; //cout << lay << endl; ll cans = Secret(ht[lay][L], ht[lay][R]); return cans; }