#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9,N = 40001; #include "floppy.h" struct ST { vector<pii> t; ST(){} ST(int nn) { t.assign(4*nn+1,{-inf,0}); } void update(int node,int l,int r,int p,pii v) { if (l == r) { t[node] = v; return; } int m = (l+r) >> 1; if (p <= m) update(2*node,l,m,p,v); else update(2*node+1,m+1,r,p,v); t[node] = max(t[2*node],t[2*node+1]); } pii query(int node,int l,int r,int L,int R) { if (l > R || r < L) return {-inf,0}; if (l >= L && r <= R) return t[node]; int m = (l+r) >> 1; return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R)); } } st; int n; string msg; void constructtree(int l,int r) { int root = st.query(1,1,n,l,r).ss; msg+='0'; if (root > l) constructtree(l,root-1); msg+='1'; if (root < r) constructtree(root+1,r); } void read_array(int subtask_id, const std::vector<int> &v) { n = big(v); st = ST(n); for (int i=1;i<=n;i++) st.update(1,1,n,i,{v[i-1],i}); constructtree(1,n); save_to_floppy(msg); } int timer = 1; vi edges[N]; string MSG; vi match; int deconstruct(int l,int r) { int haha = match[l]; int sol = -1; if (haha > l+1) { sol = deconstruct(l+1,haha-1); } int me = timer++; if (haha > l+1) { edges[me].push_back(sol); } if (haha < r) { int sag = deconstruct(haha+1,r); edges[me].push_back(sag); } return me; } int tin[N],tout[N],up[N][18]; void dfs(int node,int p) { tin[node] = timer++; up[node][0] = p; for (int i=1;i<18;i++) up[node][i] = up[up[node][i-1]][i-1]; for (auto it : edges[node]) { if (it != p) dfs(it,node); } tout[node]= timer++; } bool anc(int a,int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a,int b) { if (anc(a,b)) return a; if (anc(b,a)) return b; for (int i = 17;i>=0;i--) { if (!anc(up[a][i],b)) a = up[a][i]; } return up[a][0]; } std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { MSG = bits; int q = big(a); match.resize(big(bits)); stack<int> stk; for (int i = 0;i<big(bits);i++) { if (bits[i] == '0') { stk.push(i); }else { match[stk.top()] = i; stk.pop(); } } int root = deconstruct(0,big(MSG)-1); timer = 1; dfs(root,root); vi ans(q); for (int i = 0;i<q;i++) { ans[i] = lca(a[i]+1,b[i]+1); } return ans; }