#include<bits/stdc++.h> #include "floppy.h" using namespace std; int n,id=0,node=0; vector<vector<int>>table(20,vector<int>(1e5+10)),up(1e5+10,vector<int>(20,-1)); vector<int>depth(1e5+10,0),pos(1e5+10,0),val(1e5+10,0),arr; string bits=""; int get(int l,int r) { int lg=31-__builtin_clz(r-l+1); int L=table[l][lg],R=table[r-(1<<lg)+1][lg]; if(arr[L]>arr[R]) return L; return R; } void rec(int l,int r) { if(l>r) return; int mx=get(l,r); if(l==mx) bits+='0'; else bits+='1'; if(r==mx) bits+='0'; else bits+='1'; rec(l,mx-1); rec(mx+1,r); } void read_array(int subtask_id, const vector<int> &v) { arr=v; n=(int)v.size(); for(int i=0;i<n;++i) table[i][0]=i; for(int j=1;j<20;++j) { for(int i=0;i+(1<<j)-1<n;++i) { int a=table[i][j-1]; int b=table[i+(1<<(j-1))][j-1]; table[i][j]=(arr[a]>arr[b])?a:b; } } rec(0,n-1); save_to_floppy(bits); } void dfs(int u) { for(int i=1;i<20;i++) if(~up[i-1][u]) up[i][u]=up[i-1][up[i-1][u]]; if(bits[u<<1]=='1') { node++; up[0][node]=u; depth[node]=depth[u]+1; dfs(node); } val[u]=id; pos[id]=u; id++; if(bits[u<<1|1]=='1') { node++; up[0][node]=u; depth[node]=depth[u]+1; dfs(node); } } int lca(int a,int b) { if(depth[a]<depth[b]) swap(a,b); int need=depth[a]-depth[b]; for(int i=19;~i;--i) { if((1<<i)<=need) { need-=(1<<i); a=up[i][a]; } } if(a==b) return a; for(int i=19;~i;--i) if(up[i][a]!=up[i][b]) { a=up[i][a]; b=up[i][b]; } return up[0][a]; } vector<int> solve_queries(int subtask_id, int N, const string &ss, const vector<int> &a, const vector<int> &b) { n=N; bits=ss; id=0,node=0; dfs(0); vector<int>ans; for(int i=0;i<(int)a.size();i++) { int L,R; L=val[a[i]],R=val[b[i]]; int lc=lca(L,R); ans.emplace_back(pos[lc]); } return ans; }