File size: 3,912 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | #include <bits/stdc++.h>
using namespace std;
struct Segment {
int a;
int k;
vector<int> bits;
int preNode;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long L, R;
if (!(cin >> L >> R)) return 0;
// Step 1: Decompose [L, R] into dyadic intervals [a*2^k, (a+1)*2^k - 1]
vector<Segment> segs;
long long cur = L;
while (cur <= R) {
int k = __builtin_ctzll(cur);
while (cur + (1LL << k) - 1 > R) --k;
Segment s;
s.a = int(cur >> k);
s.k = k;
segs.push_back(s);
cur += (1LL << k);
}
// Step 2: Build trie of proper prefixes of all a's (binary, MSB to LSB)
struct TrieNode {
int child[2];
TrieNode() { child[0] = child[1] = 0; }
};
vector<TrieNode> trie(2); // index 0 unused, 1 = root (start)
int root = 1;
int nextNode = 1; // last used index in trie
int Kmax = 0;
for (auto &seg : segs) {
int a = seg.a;
// get bits of a, MSB -> LSB
string tmp;
while (a > 0) {
tmp.push_back(char('0' + (a & 1)));
a >>= 1;
}
reverse(tmp.begin(), tmp.end());
seg.bits.clear();
for (char c : tmp) seg.bits.push_back(c - '0');
int len = (int)seg.bits.size();
int curNode = root;
if (len > 1) {
for (int i = 0; i < len - 1; ++i) {
int b = seg.bits[i];
if (trie[curNode].child[b] == 0) {
trie.push_back(TrieNode());
trie[curNode].child[b] = ++nextNode;
}
curNode = trie[curNode].child[b];
}
}
// preNode is node corresponding to prefix of length len-1 (or root if len==1)
seg.preNode = (len == 1) ? root : curNode;
Kmax = max(Kmax, seg.k);
}
int prefixN = nextNode; // nodes 1..prefixN are prefix-trie nodes
// Step 3: Create suffix chain nodes Suf[0..Kmax], Suf[0] is F (end)
int totalNodes = prefixN + (Kmax + 1);
vector<int> sufId(Kmax + 1);
for (int d = 0; d <= Kmax; ++d) {
sufId[d] = prefixN + 1 + d;
}
int F = sufId[0];
// Step 4: Build adjacency lists
vector<vector<pair<int,int>>> g(totalNodes + 1); // (to, bit)
// Prefix edges from trie
for (int i = 1; i <= prefixN; ++i) {
for (int b = 0; b <= 1; ++b) {
int ch = trie[i].child[b];
if (ch != 0) {
g[i].push_back({ch, b});
}
}
}
// Suffix chain edges
for (int d = 1; d <= Kmax; ++d) {
int u = sufId[d];
int v = sufId[d - 1];
g[u].push_back({v, 0});
g[u].push_back({v, 1});
}
// Segment-specific final edges
for (auto &seg : segs) {
int len = (int)seg.bits.size();
int lastBit = seg.bits[len - 1];
int pre = seg.preNode;
int dest = (seg.k == 0) ? F : sufId[seg.k];
g[pre].push_back({dest, lastBit});
}
// Step 5: Deduplicate edges with same (to, bit) from each node
for (int u = 1; u <= totalNodes; ++u) {
auto &vec = g[u];
sort(vec.begin(), vec.end(), [](const pair<int,int>&x, const pair<int,int>&y){
if (x.second != y.second) return x.second < y.second;
return x.first < y.first;
});
vec.erase(unique(vec.begin(), vec.end(), [](const pair<int,int>&x, const pair<int,int>&y){
return x.first == y.first && x.second == y.second;
}), vec.end());
}
// Output
cout << totalNodes << '\n';
for (int i = 1; i <= totalNodes; ++i) {
auto &vec = g[i];
cout << (int)vec.size();
for (auto &e : vec) {
cout << ' ' << e.first << ' ' << e.second;
}
cout << '\n';
}
return 0;
} |