docker_space/frontier_cs_7/debug3.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L = 577837, R = 979141;

    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto nn = [&]() -> int { adj.emplace_back(); return n++; };

    int END = nn();
    int START = nn();

    map<int,int> fc;
    fc[0] = END;
    set<int> free_nodes_used_directly; // free nodes referenced by range nodes
    
    function<int(int)> getF = [&](int k) -> int {
        if (fc.count(k)) return fc[k];
        int ch = getF(k-1), u = nn();
        adj[u].push_back({ch, 0});
        adj[u].push_back({ch, 1});
        return fc[k] = u;
    };

    map<tuple<int,int,int>,int> rc;
    function<int(int,int,int)> gr = [&](int k, int lo, int hi) -> int {
        if (lo > hi) return -1;
        if (k == 0) return (lo == 0 && hi == 0) ? END : -1;
        if (lo == 0 && hi == (1<<k)-1) {
            free_nodes_used_directly.insert(k);
            return getF(k);
        }
        auto key = make_tuple(k, lo, hi);
        auto it = rc.find(key);
        if (it != rc.end()) return it->second;
        int mid = 1 << (k-1);
        int left = -1, right = -1;
        if (lo <= min(hi, mid-1))
            left = gr(k-1, lo, min(hi, mid-1));
        if (max(lo, mid) <= hi)
            right = gr(k-1, max(lo, mid) - mid, hi - mid);
        if (left == -1 && right == -1) return rc[key] = -1;
        int u = nn();
        if (left != -1) adj[u].push_back({left, 0});
        if (right != -1) adj[u].push_back({right, 1});
        return rc[key] = u;
    };

    int lenL = 32 - __builtin_clz(L), lenR = 32 - __builtin_clz(R);
    for (int len = lenL; len <= lenR; len++) {
        int rs = 1 << (len-1), re = (1<<len)-1;
        int cL = max(L, rs), cR = min(R, re);
        if (cL > cR) continue;
        int target = (len == 1) ? END : gr(len-1, cL - rs, cR - rs);
        if (target != -1) adj[START].push_back({target, 1});
    }

    cout << "Free nodes directly used by range nodes: ";
    for (int k : free_nodes_used_directly) cout << k << " ";
    cout << endl;
    
    // Check which free nodes are in the chain but not directly referenced
    cout << "All free nodes in chain: ";
    for (auto& [k, id] : fc) cout << k << " ";
    cout << endl;
    
    // For each range node, show its children types
    cout << "\nRange node analysis:" << endl;
    for (auto& [key, id] : rc) {
        if (id == -1) continue;
        auto [k, lo, hi] = key;
        cout << "  Range(" << k << "," << lo << "," << hi << ") node=" << id << " edges:";
        for (auto& e : adj[id]) {
            // Check if child is a free node
            bool is_free = false;
            for (auto& [fk, fid] : fc) {
                if (fid == e.to) { cout << " F[" << fk << "](" << e.w << ")"; is_free = true; break; }
            }
            if (!is_free) {
                // Check if child is END
                if (e.to == END) cout << " END(" << e.w << ")";
                else {
                    // Find child range
                    for (auto& [key2, id2] : rc) {
                        if (id2 == e.to) {
                            auto [k2, lo2, hi2] = key2;
                            cout << " R(" << k2 << "," << lo2 << "," << hi2 << ")(" << e.w << ")";
                            break;
                        }
                    }
                }
            }
        }
        cout << endl;
    }

    return 0;
}