#include<bits/stdc++.h> #include <stdlib.h> #include <string.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,0)); vector<int>depth(1e5+10),pos(1e5+10),val(1e5+10),arr(1e5+10); 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) { n=v.size(); arr=v; bits.clear(); for(int i=0;i<n;++i) table[i][0]=i; for(int j=1;j<20;++j) { for(int i=0;i<n;++i) { int nxt=i+(1<<(j-1)); table[i][j]=table[i][j-1]; if(nxt<n) { int a=table[i][j-1],b=table[nxt][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++) 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 nn,const string &s,const vector<int>&a,const vector<int>&b) { n=nn, bits=s; id=0,node=0; dfs(0); vector<int>ans; for(int i=0;i<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; }