#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]; calculate(0, n-1, 0); pref[0] = a[0]; for(int i = 1; i < min(n, 4); i++) pref[i] = Secret(pref[i-1], a[i]); suf[n-1] = a[n-1]; for(int i = n-2; i >= max(0, n-4); 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"; while(true); //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(r-l+1 <= 2){ int ans = a[l]; for(int i = l+1; i <= r; i++) ans = Secret(ans, a[i]); return ans; //I will deal with this later } if(l == 0 && r <= 3) return pref[r]; if(r == n-1 && l >= n-4) return suf[l]; return solve(0, n-1, 0, l, r); }