#include "secret.h" const int NMAX = 1000; const int LOGMAX = 9; int a[NMAX + 1], n; int st[LOGMAX + 1][NMAX + 1]; int mask[NMAX + 1]; void precalc(int left, int right, int k) { if(left == right) { return; } int mid = (left + right) / 2; st[k][mid] = a[mid]; for(int i = mid - 1; i >= left; i--) { st[k][i] = Secret(a[i], st[k][i + 1]); } st[k][mid + 1] = a[mid + 1]; for(int i = mid + 2; i <= right; i++) { st[k][i] = Secret(st[k][i - 1], a[i]); } for(int i = mid + 1; i <= right; i++) { mask[i] |= (1 << k); } precalc(left, mid, k + 1); precalc(mid + 1, right, k + 1); } void Init(int N, int A[]) { for(int i = 1; i <= N; i++) { a[i] = A[i - 1]; } n = N; precalc(1, n, 0); } int Query(int L, int R) { L++; R++; if(L == R) { return a[L]; } int k = __builtin_ctz(mask[L] ^ mask[R]); return Secret(st[k][L], st[k][R]); }