#include "secret.h" #include<bits/stdc++.h> using namespace std; int n, a[1005], f[20][1005], pref[25], suf[25]; void calculate(int l, int r, int depth) { if(r-l+1 <= 4) return; int mid = (l+r)/2; f[depth][mid] = a[mid]; for(int i = mid-1; i >= l; i--) f[depth][i] = Secret(a[i], f[depth][i+1]); f[depth][mid+1] = a[mid+1]; for(int i = mid+2; i <= r; i++) f[depth][i] = Secret(f[depth][i-1], a[i]); calculate(l, mid, depth+1); calculate(mid+1, r, depth+1); } void Init(int N, int A[]) { n = N; for(int i = 0; i < n; i++) a[i] = A[i]; if(n > 4) calculate(0, n-1, 0); else{ pref[0] = a[0]; for(int i = 1; i < n; i++) pref[i] = Secret(pref[i-1], a[i]); suf[n-1] = a[n-1]; for(int i = n-2; i >= 0; i--) suf[i] = Secret(a[i], suf[i+1]); } } int solve(int l, int r, int depth, int tl, int tr) { if(r-l+1 <= 4){ cout<<"Wtf"; exit(1); //This case should never happen return -1; } int mid = (l+r)/2; if(tr < mid) return solve(l, mid, depth+1, tl, tr); else if(tr == mid) return f[depth][tl]; else if(tl <= mid) return Secret(f[depth][tl], f[depth][tr]); else if(tl == mid+1) return f[depth][tr]; else return solve(mid+1, r, depth+1, tl, tr); } int Query(int l, int r) { if(l == r) return a[l]; if(l + 1 == r) return Secret(a[l], a[r]); if(n <= 4){ if(l == 0) return pref[r]; else return suf[l]; //Trust me bro } return solve(0, n-1, 0, l, r); }