#include "floppy.h" // Include the header provided by the problem statement
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <memory> // Required for unique_ptr if used, though direct arrays/vectors are fine too
// --- Global data for Interaction 1 (will be lost before Interaction 2) ---
// Not strictly necessary to be global, can be local to read_array
namespace interaction1 {
std::vector<int> left_child;
std::vector<int> right_child;
std::vector<int> parent;
std::string encoded_bits;
// Recursive function to encode the tree structure (preorder)
void encode_tree(int u) {
if (u == -1) {
encoded_bits += '0';
return;
}
encoded_bits += '1';
encode_tree(left_child[u]);
encode_tree(right_child[u]);
}
} // namespace interaction1
// --- Global data for Interaction 2 ---
namespace interaction2 {
int N;
std::vector<int> left_child;
std::vector<int> right_child;
std::vector<int> parent; // Parent needed for LCA precomputation
std::vector<int> node_to_original_index;
std::vector<int> original_index_to_node;
std::string::const_iterator bit_iterator; // To iterate through the bits string
// LCA related data (using binary lifting)
const int MAX_LOG_N = 18; // ceil(log2(40000)) + a bit extra
std::vector<std::vector<int>> up; // up[k][u] = 2^k-th ancestor of u
std::vector<int> depth;
int current_node_id = 0;
int current_original_index = 0;
// Recursive function to decode the bit string and build the tree structure
int decode_tree(const std::string& bits) {
if (bit_iterator == bits.end() || *bit_iterator == '0') {
++bit_iterator; // Consume the '0'
return -1; // Represents a null child
}
++bit_iterator; // Consume the '1'
int node_id = current_node_id++;
left_child[node_id] = decode_tree(bits);
right_child[node_id] = decode_tree(bits);
// Set parent pointers during reconstruction
if (left_child[node_id] != -1) {
parent[left_child[node_id]] = node_id;
}
if (right_child[node_id] != -1) {
parent[right_child[node_id]] = node_id;
}
return node_id;
}
// Inorder traversal to assign original indices
void assign_indices_inorder(int u) {
if (u == -1) {
return;
}
assign_indices_inorder(left_child[u]);
// Assign original index during the inorder visit
node_to_original_index[u] = current_original_index;
original_index_to_node[current_original_index] = u;
current_original_index++;
assign_indices_inorder(right_child[u]);
}
// Depth First Search to compute depths and immediate parents for LCA
void dfs_lca(int u, int p, int d) {
depth[u] = d;
up[0][u] = p; // Immediate parent (or -1 for root)
if (left_child[u] != -1) {
dfs_lca(left_child[u], u, d + 1);
}
if (right_child[u] != -1) {
dfs_lca(right_child[u], u, d + 1);
}
}
// Precompute LCA using binary lifting
void build_lca(int root) {
depth.assign(N, 0);
up.assign(MAX_LOG_N, std::vector<int>(N, -1));
dfs_lca(root, -1, 0); // Compute depth and up[0]
for (int k = 1; k < MAX_LOG_N; ++k) {
for (int u = 0; u < N; ++u) {
if (up[k - 1][u] != -1) {
up[k][u] = up[k - 1][up[k - 1][u]];
}
}
}
}
// Query LCA
int get_lca(int u, int v) {
if (depth[u] < depth[v]) {
std::swap(u, v);
}
// Bring u to the same depth as v
for (int k = MAX_LOG_N - 1; k >= 0; --k) {
if (up[k][u] != -1 && depth[up[k][u]] >= depth[v]) {
u = up[k][u];
}
}
if (u == v) {
return u;
}
// Lift u and v together
for (int k = MAX_LOG_N - 1; k >= 0; --k) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
// Now up[0][u] == up[0][v] is the LCA
return up[0][u];
}
} // namespace interaction2
// --- Interaction 1 Implementation ---
void read_array(int subtask_id, const std::vector<int>& v) {
int n = v.size();
interaction1::left_child.assign(n, -1);
interaction1::right_child.assign(n, -1);
interaction1::parent.assign(n, -1);
interaction1::encoded_bits = "";
// Build Cartesian Tree using O(N) stack method
std::stack<int> s;
for (int i = 0; i < n; ++i) {
int last_popped = -1;
while (!s.empty() && v[s.top()] < v[i]) {
last_popped = s.top();
s.pop();
}
interaction1::left_child[i] = last_popped;
if (last_popped != -1) {
interaction1::parent[last_popped] = i;
}
if (!s.empty()) {
interaction1::right_child[s.top()] = i;
interaction1::parent[i] = s.top();
}
s.push(i);
}
// Find the root (the node with no parent)
int root = -1;
for (int i = 0; i < n; ++i) {
if (interaction1::parent[i] == -1) {
root = i;
break;
}
}
// Encode the tree structure
interaction1::encode_tree(root);
// Save the bits
save_to_floppy(interaction1::encoded_bits);
assert (interaction1::encoded_bits.size () <= v.size () * 2);
}
// --- Interaction 2 Implementation ---
std::vector<int> solve_queries(int subtask_id, int N_in, const std::string& bits, const std::vector<int>& a, const std::vector<int>& b) {
interaction2::N = N_in;
interaction2::left_child.assign(N_in, -1);
interaction2::right_child.assign(N_in, -1);
interaction2::parent.assign(N_in, -1); // Important for LCA precomputation
interaction2::node_to_original_index.assign(N_in, -1);
interaction2::original_index_to_node.assign(N_in, -1);
interaction2::bit_iterator = bits.begin();
interaction2::current_node_id = 0; // Reset counters for reconstruction
interaction2::current_original_index = 0;
// 1. Reconstruct the tree structure from bits
int root = interaction2::decode_tree(bits);
// The parent array is partially filled by decode_tree, root's parent remains -1.
// 2. Assign original indices using inorder traversal
interaction2::assign_indices_inorder(root);
// 3. Precompute LCA data structures
interaction2::build_lca(root);
// 4. Answer queries
int M = a.size();
std::vector<int> results(M);
for (int i = 0; i < M; ++i) {
int u_orig_idx = a[i];
int v_orig_idx = b[i];
// Handle query for single element range
if (u_orig_idx == v_orig_idx) {
results[i] = u_orig_idx;
continue;
}
int u_node = interaction2::original_index_to_node[u_orig_idx];
int v_node = interaction2::original_index_to_node[v_orig_idx];
int lca_node = interaction2::get_lca(u_node, v_node);
results[i] = interaction2::node_to_original_index[lca_node];
}
return results;
}
