#include <bits/stdc++.h> #include "secret.h" #define endl '\n' #define fi first #define se second #define eb emplace_back #define pb push_back #define ce cout << endl #define ALL(A) A.begin(), A.end() #define FOR(i, l, r) for (int i = l; i <= r; i++) #define FOR2(i, l, r) for (int i = l; i >= r; i--) using namespace std; using ll = long long; using pll = pair<ll, ll>; using pii = pair<int, int>; using str = string; using ull = unsigned long long; using ld = long double; const int INF = 1e9; const int MAXN = 1000; const int LOGN = 11; const int heavy = 500; const int MOD = 1e9 + 7; int dx[] = {0, 1, 0, -1}; // east, south, west, north int dy[] = {1, 0, -1, 0}; // T_Danh - Tri An High School int X[MAXN]; int dat[LOGN][MAXN]; int mask[MAXN]; void divi(int l, int r, int lev) { if (l == r) return; int m = (l + r) >> 1; dat[lev][m] = X[m]; FOR2(i,m - 1 , l) { dat[lev][i] = Secret(X[i], dat[lev][i + 1]); } dat[lev][m + 1] = X[m + 1]; FOR(i,m + 2 , r) { dat[lev][i] = Secret(dat[lev][i - 1], X[i]); } FOR(i,m + 1 , r) mask[i] ^= (1 << lev); divi(l, m, lev + 1); divi(m + 1, r, lev + 1); } void Init(int N, int A[]) { FOR(i,0,N -1) X[i] = A[i]; divi(0, N - 1, 0); } int Query(int L, int R) { if (L == R) return X[L]; int lev = __builtin_ctz(mask[L] ^ mask[R]); return Secret(dat[lev][L], dat[lev][R]); } // int main() { // ios::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // int t = 1; // while (t--) solve(); // return 0; // }