#include "secret.h" #include <bits/stdc++.h> using namespace std; #define MOD 1000000007 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define FOR(i, s, e) for(int i = s; i < e; i++) #define RFOR(i, s, e) for(int i = e-1; i >= s; i--) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; int n; vi arr; const int MN = 1005; int dp[11][MN]; void precompute(int l, int r, int t) { int m = (l + r) / 2; dp[t][m] = arr[m]; if(l == r) { return; } //cerr<<l<<' '<<r<<endl; RFOR(i, l, m) { dp[t][i] = Secret(arr[i], dp[t][i+1]); } dp[t][m+1] = arr[m+1]; FOR(i, m+2, r+1) { dp[t][i] = Secret(dp[t][i-1], arr[i]); } precompute(l, m, t+1); precompute(m+1, r, t+1); } void Init(int N, int A[]) { n = N; arr = vi(n); REP(i, n) { arr[i] = A[i]; } memset(dp, 0, sizeof(dp)); precompute(0, n-1, 0); /* REP(i, 10) { REP(j, n) { cerr<<dp[i][j]<<' '; } cerr<<endl; } */ } int qry(int l, int r, int t, int s, int e) { int m = (l + r) / 2; if(l == r) { //cerr<<l<<' '<<r<<' '<<t<<' '; return arr[s]; } if(m >= e) { return qry(l, m, t+1, s, e); } else if(m < s) { return qry(m+1, r, t+1, s, e); } //cerr<<l<<' '<<r<<' '<<t<<' '; return Secret(dp[t][s], dp[t][e]); } int Query(int L, int R) { return qry(0, n-1, 0, L, R); }