#include "floppy.h" #include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; //#define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() const int LG = 20; template <typename T> struct SparseTableMax{ vector<vector<T>> st; SparseTableMax(const vector<T> &a){ int n = sz(a), lg = __lg(n) + 1; st.resize(lg); st[0] = a; for(int bit = 1; bit < lg; bit++){ st[bit].resize(n - (1 << bit) + 1); for(int v = 0; v + (1 << bit) - 1 < n; v++){ st[bit][v] = max(st[bit - 1][v], st[bit - 1][v + (1 << (bit - 1))]); } } } inline T query(int l, int r){ int lg = __lg(r - l + 1); return max(st[lg][l], st[lg][r - (1 << lg) + 1]); } }; template <typename T> struct SparseTableMin{ vector<vector<T>> st; SparseTableMin(const vector<T> &a){ int n = sz(a), lg = __lg(n) + 1; st.resize(lg); st[0] = a; for(int bit = 1; bit < lg; bit++){ st[bit].resize(n - (1 << bit) + 1); for(int v = 0; v + (1 << bit) - 1 < n; v++){ st[bit][v] = min(st[bit - 1][v], st[bit - 1][v + (1 << (bit - 1))]); } } } inline T query(int l, int r){ int lg = __lg(r - l + 1); return min(st[lg][l], st[lg][r - (1 << lg) + 1]); } }; // cartesian tree : (sol_subtree)sağ_subtree void read_array(int sid, const vi &vec){ vector<pii> temp(sz(vec)); for(int i = 0; i < sz(vec); i++){ temp[i] = {vec[i], i}; } SparseTableMax<pii> st(temp); string msg = ""; function<void(int, int)> build_tree = [&](int le, int ri) -> void { if(le > ri || le < 0 || ri >= sz(temp)) return; int idx = st.query(le, ri).se; msg += '0'; // ( if(idx > le) build_tree(le, idx - 1); // sol_subtree msg += '1'; // ) if(idx < ri) build_tree(idx + 1, ri); // sağ subtree return; }; build_tree(0, sz(temp) - 1); save_to_floppy(msg); return; } vi solve_queries(int sid, int n, const string &msg, const vi &left, const vi &right){ vvi adj(n); vi close(sz(msg)); stack<int> s; for(int i = 0; i < sz(msg); i++){ if(msg[i] == '1'){ close[s.top()] = i; s.pop(); } else{ s.emplace(i); } } int timer = 0, root = 0; // dfs-order, (sol)sağ diye gittiğim için benim aynı şekilde geri çözünce dfs-order'ım array indeximle aynı oluyor function<int(int, int)> deconstruct = [&](int le, int ri) -> int { int lefst = -1, rigst = -1, go = close[le]; if(le + 1 <= go - 1){ lefst = deconstruct(le + 1, go - 1); } int myidx = timer++; if(le == 0 && ri == sz(msg) - 1){ root = myidx; } if(lefst != -1){ adj[myidx].emplace_back(lefst); } if(go + 1 <= ri){ rigst = deconstruct(go + 1, ri); adj[myidx].emplace_back(rigst); } return myidx; }; deconstruct(0, sz(msg) - 1); vi dep(n), tin(n); vector<pii> t2v(2 * n); timer = 0; vvi lift(n, vi(LG)); function<void(int, int)> dfs = [&](int v, int p) -> void { tin[v] = timer; t2v[timer++] = {dep[v], v}; /*lift[v][0] = p; for(int bit = 1; bit < LG; bit++){ lift[v][bit] = lift[lift[v][bit - 1]][bit - 1]; }*/ for(int &u : adj[v]){ dep[u] = dep[v] + 1; dfs(u, v); t2v[timer++] = {dep[v], v}; } return; }; dfs(root, root); SparseTableMin<pii> st(t2v); auto query = [&](int l, int r) -> int { if(tin[l] > tin[r]) swap(l, r); return st.query(tin[l], tin[r]).se; }; auto kth = [&](int a, int k) -> int { for(int bit = LG - 1; bit >= 0; bit--){ if((k >> bit) & 1){ a = lift[a][bit]; } } return a; }; auto find_lca = [&](int a, int b) -> int { if(dep[a] < dep[b]) swap(a, b); a = kth(a, dep[a] - dep[b]); if(a == b) return a; for(int bit = LG - 1; bit >= 0; bit--){ if(lift[a][bit] != lift[b][bit]){ a = lift[a][bit]; b = lift[b][bit]; } } return lift[a][0]; }; vi ans(sz(left)); for(int i = 0; i < sz(left); i++){ ans[i] = query(left[i], right[i]); //ans[i] = find_lca(left[i], right[i]); } return ans; } /* inline void solve(){ int n, q; cin >> n >> q; vi a(n), ql(q), qr(q); for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < q; i++){ cin >> ql[i] >> qr[i]; } read_array(-1, a); vi res = solve_queries(-1, n, msg, ql, qr); for(int i = 0; i < sz(res); i++){ cout << res[i] << " "; } cout << "\n"; return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; } */