アプローチ

共通接尾辞の再帰的な構築。（実質は有限状態オートマトン）

直接力技を使う？二分木を作れば良いが、ノードが多すぎて無理。

しかし、多くの部分木が繰り返し利用されるため、共有すれば良い。詳細はコードで確認。

実装

verify_length 関数

void verify_length(int start, int end, int left, int right) {
    int mid = (start + end) / 2;
    if (start == left && end == right) {
        int length = 0;
        int temp = end - start + 1; // 区間の長さ
        while (temp > 0) {
            length++;
            temp /= 2;
        }
        if (length > maxLen) maxLen = length; // 最大長更新
        return;
    }
    if (right <= mid)
        verify_length(start, mid, left, right);
    else if (left > mid)
        verify_length(mid + 1, end, left, right);
    else {
        verify_length(start, mid, left, mid);
        verify_length(mid + 1, end, mid + 1, right);
    }
}

区間 \([left,right]\) の最大バイナリ長を計算する。（実際には単純な for ループでも可能だが、同じ構造なのでそのまま使用）

計算量：\(O(\log R)\)。

construct_tree 関数 - 構築

void construct_tree(int node, int s, int e, int l, int r, bool isNew, pair<int, int> prevNode) {
    int mid = (s + e) / 2;
    if (s == l && e == r) { // 現在の区間が完全に目的区間に含まれる場合
        int length = 0;
        int temp = e - s + 1;
        while (temp > 0) {
            length++;
            temp /= 2;
        }
        nodes[prevNode.first].push_back(make_pair(length, prevNode.second));
        return;
    }
    if (isNew) node = ++nodeCount; // 新しいノードが必要な場合
    if (isNew && prevNode.first != 0) nodes[prevNode.first].push_back(make_pair(node, prevNode.second));

    if (l > mid)
        construct_tree(node, mid + 1, e, l, r, true, make_pair(node, 1));
    else if (r <= mid)
        construct_tree(node, s, mid, l, r, false, make_pair(node, 0));
    else {
        construct_tree(node, s, mid, l, mid, false, make_pair(node, 0));
        construct_tree(node, mid + 1, e, mid + 1, r, true, make_pair(node, 1));
    }
}

説明：

• node: 処理中のノード番号；
• s,e: 現在考慮している値範囲；
• l,r: 目標区間 \([L,R]\)；
• isNew: 新しいノードが必要かどうか；
• prevNode: 前回の状態（ノード番号，辺の重み）。

論理：

1. 完全被覆の場合：現在の区間 \([s,e]\) が \([l,r]\) 内であれば、接尾辞チェーンに対応する長さのノードに直接接続。
2. 部分被覆の場合：

• 目標区間が右半分に完全に含まれる場合：新しいノードを作成（isNew=true）、辺の重みは1；
• 目標区間が左半分に完全に含まれる場合：既存のノードを再利用、辺の重みは0；
• 中点を跨ぐ場合：左右それぞれを別途処理。

計算量: \(O(\log R)\)。

メイン関数

signed main() {
    cin >> L >> R;
    maxLen = 0;
    verify_length(0, (1 << 20) - 1, L, R);
    // 接尾辞共有チェーンの構築
    nodeCount = maxLen;
    for (int i = 2; i <= maxLen; i++) {
        nodes[i].push_back(make_pair(i - 1, 0));
        nodes[i].push_back(make_pair(i - 1, 1));
    }
    nodeCount++;
    construct_tree(nodeCount, 0, (1 << 20) - 1, L, R, false, make_pair(0, 0));
    cout << nodeCount << '\n';
    for (int i = 1; i <= nodeCount; i++) {
        cout << nodes[i].size() << ' ';
        for (int j = 0; j < nodes[i].size(); j++) {
            cout << nodes[i][j].first << ' ' << nodes[i][j].second << ' ';
        }
        cout << '\n';
    }
    return 0;
}

全体の計算量：\(O(\log R)\)。