docker_space/frontier_cs_7/solution3.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int L, R;
    cin >> L >> R;
    
    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto addNode = [&]() { adj.emplace_back(); return n++; };
    
    int END_NODE = addNode(); // 0
    int START = addNode(); // 1
    
    // Free chain
    vector<int> freeChain(21, -1);
    freeChain[0] = END_NODE;
    for (int k = 1; k <= 20; k++) {
        int u = addNode();
        adj[u].push_back({freeChain[k-1], 0});
        adj[u].push_back({freeChain[k-1], 1});
        freeChain[k] = u;
    }
    
    // Decompose range [lo, hi] at bit length k into aligned blocks
    // Each aligned block is a prefix + free chain
    // Return list of (prefix_bits, free_length) pairs
    // A prefix of length p followed by free_length = k-p means the block starts at prefix * 2^(k-p)
    // and has 2^(k-p) elements
    
    // Standard canonical decomposition of [lo, hi] into aligned blocks
    // Returns list of (start, power) pairs where each block is [start, start + 2^power - 1]
    auto decompose = [](int lo, int hi, int k) -> vector<pair<int,int>> {
        vector<pair<int,int>> blocks;
        int x = lo;
        while (x <= hi) {
            // Find largest power p such that:
            // 1. x is a multiple of 2^p
            // 2. x + 2^p - 1 <= hi
            int p = 0;
            while (p < k && (x % (1 << (p+1)) == 0) && (x + (1 << (p+1)) - 1 <= hi)) {
                p++;
            }
            blocks.push_back({x, p});
            x += (1 << p);
        }
        return blocks;
    };
    
    int lenL = 32 - __builtin_clz(L);
    int lenR = 32 - __builtin_clz(R);
    
    for (int len = lenL; len <= lenR; len++) {
        int rs = 1 << (len-1);
        int re = (1 << len) - 1;
        int cL = max(L, rs);
        int cR = min(R, re);
        if (cL > cR) continue;
        
        int suffLen = len - 1;
        int loSuf = cL - rs;
        int hiSuf = cR - rs;
        
        if (suffLen == 0) {
            adj[START].push_back({END_NODE, 1});
            continue;
        }
        
        // Decompose [loSuf, hiSuf] into aligned blocks
        auto blocks = decompose(loSuf, hiSuf, suffLen);
        
        // For each block (start, power): the block is [start, start + 2^power - 1]
        // prefix = start >> power (the upper bits of start)
        // prefix has (suffLen - power) bits
        // The path: START -1-> prefix bits -> freeChain[power] -> ... -> END
        
        // Build a trie of the prefixes, with leaves connecting to freeChain
        // The trie is a DAG where shared prefixes share nodes
        
        // Build prefix paths
        // For each block, we have a prefix (suffLen - power bits) followed by free[power]
        
        struct TrieNode {
            int nodeId;
            int children[2]; // -1 if not set
            TrieNode() : nodeId(-1) { children[0] = children[1] = -1; }
        };
        
        vector<TrieNode> trie(1); // root
        
        for (auto& [start, power] : blocks) {
            int prefLen = suffLen - power;
            int prefix = (prefLen > 0) ? (start >> power) : 0;
            
            int cur = 0; // trie root
            for (int i = prefLen - 1; i >= 0; i--) {
                int bit = (prefix >> i) & 1;
                if (trie[cur].children[bit] == -1) {
                    trie[cur].children[bit] = trie.size();
                    trie.emplace_back();
                }
                cur = trie[cur].children[bit];
            }
            // At leaf: connect to freeChain[power]
            trie[cur].nodeId = freeChain[power];
        }
        
        // Assign DAG node IDs to trie nodes (except leaves that directly use freeChain)
        // Process trie BFS and create nodes
        // Root trie node connects to START with weight 1
        
        function<int(int)> buildTrie = [&](int t) -> int {
            if (trie[t].nodeId != -1) return trie[t].nodeId;
            if (trie[t].children[0] == -1 && trie[t].children[1] == -1) return -1;
            
            int u = addNode();
            trie[t].nodeId = u;
            
            for (int b = 0; b < 2; b++) {
                if (trie[t].children[b] != -1) {
                    int child = buildTrie(trie[t].children[b]);
                    if (child != -1) {
                        adj[u].push_back({child, b});
                    }
                }
            }
            return u;
        };
        
        int root = buildTrie(0);
        if (root >= 0) {
            adj[START].push_back({root, 1});
        }
    }
    
    // Remove unreachable
    vector<bool> reach(n, false);
    queue<int> q;
    q.push(START);
    reach[START] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : adj[u]) {
            if (!reach[e.to]) { reach[e.to] = true; q.push(e.to); }
        }
    }
    
    // Renumber
    map<int,int> newId;
    int cnt = 0;
    newId[START] = ++cnt;
    for (int i = 0; i < n; i++) {
        if (i != START && reach[i]) newId[i] = ++cnt;
    }
    
    cout << cnt << "\n";
    vector<int> inv(cnt + 1);
    for (auto& [old, nw] : newId) inv[nw] = old;
    for (int i = 1; i <= cnt; i++) {
        int u = inv[i];
        vector<pair<int,int>> edges;
        for (auto& e : adj[u]) {
            if (newId.count(e.to)) {
                edges.push_back({newId[e.to], e.w});
            }
        }
        cout << edges.size();
        for (auto& [to, w] : edges) cout << " " << to << " " << w;
        cout << "\n";
    }
    
    return 0;
}