コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに！」と思った。

問題へのリンク

問題概要

インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。

フェーズ I

ジャッジから整数 $N$ が与えられるので、それに応じて、あなたは 1 以上 50000 以下の整数 $M$ を出力する。

さらにあなたは、各 $i=1,2,\dots,M$ について $1 \le l_{i} \le r_{i} \le N$ を満たす、 $M$ 個の整数の組 $(l_{1}, r_{1}), \dots, (l_{M}, r_{M})$ を出力する。

フェーズ II

ジャッジから $Q$ 回のクエリが与えられる。各クエリでは 2 つの整数 $L, R$ が与えられる。

それに対して、あなたは 1 以上 $M$ 以下の 2 つの整数 $a,b$ を、次の条件を満たすように出力する ( $a=b$ でもよい)。

「集合 { $l_{a},l_{a}+1,\dots,r_{a}$ } と集合 { $l_{b},l_{b}+1,\dots,r_{b}$ } の和集合が、集合 { $L, L+1, \dots, R$ } と一致する。

制約

$1 \le N \le 4000$
$1 \le Q \le 10^{5}$
$1 \le L \le R \le N$

考えたこと

ここでは、Sparse Table をまったく知らなくてもアドホックに解ける思考過程を示す。

まず、この問題はインタラクティブな見た目をしているが、実質的には構築問題だといえる。つまり、整数 $N$ に応じて、次の条件を満たすような区間の集合を求めよ、ということだ。

区間の個数 $M$ は 50000 以下
任意の $1 \le L \le R \le N$ に対して、 $M$ 個の区間から上手に 2 つを選んで和集合をとると区間 $\lbrack L, R \rbrack$ に一致する

もし $M$ の大きさに上限がないならば、 $\frac{N(N+1)}{2}$ 個の区間をすべて出力すれば十分だ。実際には、許される区間の個数は、オーダー的には $O(N \log N)$ 程度だ。なお、求める区間の集合を「解集合」と呼ぶことにする。

順に考えていく

まずは長さが 1 の区間をカバーしていくことを考える。つまり、 $L = R$ という場合だ。こればかりは、すべて解集合に含める必要があるだろう。つまり、

$\lbrack 1, 1 \rbrack, \lbrack 2, 2 \rbrack, \dots, \lbrack N, N \rbrack$

をすべて解集合に含めることにする。

これらの解集合から 2 つの区間を選んで和集合をとることによって、 $\lbrack 1, 2 \rbrack, \lbrack 2, 3 \rbrack, \lbrack 3, 4 \rbrack \dots$ といった、長さ 2 の区間もすべて実現できる。そこで今度は、長さが 3 の区間を解集合に含めていくことにする。つまり、

$\lbrack 1, 3 \rbrack, \lbrack 2, 4 \rbrack, \lbrack 3, 5 \rbrack \dots, \lbrack N-2, N \rbrack$

を解集合に含めていくことにする。このとき、長さ 6 以下の区間はすべて実現できることになる。たとえば

区間 $\lbrack 19, 22 \rbrack$ は、区間 $\lbrack 19, 21 \rbrack$ と区間 $\lbrack 20, 22 \rbrack$ の和集合である

といった具合だ。このノリで、

長さ 1 の区間
長さ 3 の区間
長さ 7 の区間
長さ 15 の区間
長さ 31 の区間
...

と続けていくことで、すべての長さの区間が実現できることになる。

区間の長さが指数的に増加していることから、最終的な解集合における区間の個数は $O(N \log N)$ のオーダーの個数になる。よって大丈夫。

なお、以上の考察は、Sparse Table をまったく知らなくても十分アドホックに導出できると思う。

余談：Sparse Table

Sparse Table を踏まえると、区間の長さの系列を $1, 3, 7, 15, 31, \dots$ とするよりは、 $1, 2, 4, 8, 16, 32, \dots$ とする方が自然だ。それでももちろん正解になる。

Sparse Table の内容については、公式解説に言及がある。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    // フェーズ I
    int N;
    cin >> N;

    vector<pint> res;  // 答え
    map<pint, int> ma;  // 区間 -> 区間番号
    int len = 1;
    while (len <= N) {
        for (int i = 1; i + len - 1 <= N; ++i) {
            res.emplace_back(i, i + len - 1);
            ma[pint(i, i + len - 1)] = res.size();
        }
        len = len * 2 + 1;
    }
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); ++i)
        cout << res[i].first << " " << res[i].second << endl;

    // フェーズ II
    int Q;
    cin >> Q;
    while (Q--) {
        int u, v;
        cin >> u >> v;
        len = 1;
        while (len <= v - u + 1) len = len * 2 + 1;
        len /= 2;
        cout << ma[pint(u, u + len - 1)] << " " << ma[pint(v - len + 1, v)] << endl;
    }
}