#include <bits/stdc++.h> using namespace std; #include "secret.h" namespace local{ vector<int> v; struct Node{ int l, r; vector<int> V; Node() = default; Node(int L, int R): l(L), r(R) { V.resize(r - l + 1); int m = (l + r) / 2; V[m - l] = v[m]; V[m - l + 1] = v[m+1]; for (int i = m - l - 1; i >= 0; i--) V[i] = Secret(v[i+l], V[i+1]); for (int i = m - l + 2; i < r - l + 1; i++) V[i] = Secret(V[i-1], v[i+l]); } }; struct Segtree{ vector<Node> tree; int _n; Segtree() = default; Segtree(int N): tree(4*N), _n(N) { build(1, 0, N-1); } void build(int i, int l, int r){ tree[i] = Node(l, r); if (l == r) return; int m = (l + r) / 2; build(i<<1, l, m); build(i<<1|1, m+1, r); } int get(int tl, int tr) { return get(1, 0, _n - 1, tl, tr); } int get(int i, int l, int r, int tl, int tr){ int m = (l + r) / 2; if (l == r) return tree[i].V[0]; if (tl <= m && m < tr) return Secret(tree[i].V[tl-l], tree[i].V[tr-l]); if (tr <= m) return get(i<<1, l, m, tl, tr); return get(i<<1|1, m+1, r, tl, tr); } } st; } void Init(int N, int A[]){ local::v.resize(N); for (int i = 0; i < N; i++) local::v[i] = A[i]; local::st = local::Segtree(N); } int Query(int L, int R){ return local::st.get(L, R); }