#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "secret.h"
using namespace std;
using namespace __gnu_pbds;
// Optimization
//#pragma GCC optimize("O3")
#define endl '\n'
// Shortcut
// #define int long long
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)
// I/O & Debug
#define PrintV(a) Fora(iiii, a) cout << iiii << ' '; cout << endl;
#define PrintVl(a) Fora(iiii, a) cout << iiii << endl;
#define PrintA(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << ' '; cout << endl;
#define PrintAl(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << endl;
#define Ptest(x) return cout << x, 0;
#define gl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
/*
#define debug(args...){ string _sDEB = #args; replace(_sDEB.begin(), _sDEB.end(), ',', ' '); stringstream _ssDEB(_sDEB); istream_iterator<string> _itDEB(_ssDEB); DEB(_itDEB, args); }
void DEB(istream_iterator<string> it) {}
template<typename T, typename... Args>
void DEB(istream_iterator<string> it, T a, Args... args){
cout << *it << " = " << a << endl;
DEB(++it, args...);
}
*/
// Functions
//#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define bend(a) a.begin(), a.end()
#define rbend(a) a.rbegin(), a.rend()
#define mset(a) memset(a, 0, sizeof(a))
#define mset1(a) memset(a, 1, sizeof(a))
#define msetn1(a) memset(a, -1, sizeof(a))
#define msetinf(a) memset(a, 0x3f, sizeof(a))
#define gcd __gcd
#define __builtin_popcount __builtin_popcountll
//mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
//int randt(int l, int r){ return (rando() % (r - l + 1) + l); }
// Data Structure
#define pque priority_queue
#define mts multiset
#define y0 _y0_
#define y1 _y1_
#define div divi
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;
const int N = 1e3, PWN = 1024, LV = 11;
int mod = 1e9 + 7, mod1 = 998244353, mod2 = 1e9 + 9, inf = 1e9;
ll infll = 1e18 + 7;
//int Secret(int X, int Y);
int b[N];
int table[LV][PWN];
int maxlev, size;
map <pair <int, int>, int> mpp;
void build(int lev = 0, int l = 0, int r = size){
int m = (l + r - 1) >> 1;
table[lev][m] = b[m];
FordE(i, m - 1, l){
if (mpp.find({i, m}) == mpp.end()){
table[lev][i] = Secret(b[i], table[lev][i + 1]);
mpp[{i, m}] = table[lev][i];
}
else{
table[lev][i] = mpp[{i, m}];
}
}
if (m + 1 < r){
table[lev][m + 1] = b[m + 1];
For(i, m + 2, r){
if (mpp.find({m + 1, i}) == mpp.end()){
table[lev][i] = Secret(table[lev][i - 1], b[i]);
mpp[{m + 1, i}] = table[lev][i];
}
else{
table[lev][i] = mpp[{m + 1, i}];
}
}
}
if (l + 1 != r){
build(lev + 1, l, m + 1);
build(lev + 1, m + 1, r);
}
}
void Init(int n, int a[]){
For(i, 0, n){
b[i] = a[i];
}
size = n;
maxlev = __builtin_clz(n) ^ 31;
if ((1 << maxlev) != n){
size = 1 << ++maxlev;
}
build();
// For(lev, 0, maxlev){
// For(i, 0, n){
// cout << lev << ' ' << i << ' ' << table[lev][i] << endl;
// }
// }
}
int Query(int l, int r){
if (l == r){
return b[l];
}
int k2 = __builtin_clz(l ^ r) ^ 31;
int lev = maxlev - 1 - k2;
int m = ((r >> k2) << k2) - 1;
// cout << "Q " << l << ' ' << r << ' ' << k2 << ' ' << lev << endl;
int ans = table[lev][l];
if (r > m){
ans = Secret(ans, table[lev][r]);
}
return ans;
}
// DEBUGGING SECTION ======================================================================================================
//int n, q;
//int a[N];
//
//int Secret(int X, int Y){
// return (X + 2 * (Y / 2) < inf) ? (X + 2 * (Y / 2)) : inf;
//}
//
//signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// cin >> n;
// For(i, 0, n){
// cin >> a[i];
// }
// Init(n, a);
// cin >> q;
// while (q--){
// int l, r; cin >> l >> r; cout << Query(l, r) << endl;
// }
//}
/*
==================================+
INPUT: |
------------------------------ |
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
------------------------------ |
==================================+
OUTPUT: |
------------------------------ |
------------------------------ |
==================================+
*/
Compilation message
secret.cpp:94:44: error: reference to 'size' is ambiguous
void build(int lev = 0, int l = 0, int r = size){
^~~~
secret.cpp:91:13: note: candidates are: int size
int maxlev, size;
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from secret.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:128:5: error: reference to 'size' is ambiguous
size = n;
^~~~
secret.cpp:91:13: note: candidates are: int size
int maxlev, size;
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from secret.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
secret.cpp:131:9: error: reference to 'size' is ambiguous
size = 1 << ++maxlev;
^~~~
secret.cpp:91:13: note: candidates are: int size
int maxlev, size;
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from secret.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
