公式解説と同様に、 \(l\) 以上 \(r\) 以下の整数全体からなる集合を区間 \([l, r]\) と呼び、その長さを \(r - l + 1\) で定義します。

\(N \geq 2\) のとき、区間 \([1, N]\) に含まれる任意の区間は以下のいずれかに分類されます。 ここで、 \(m = \lfloor \frac{1 + N}{2} \rfloor\) です。

1. 区間 \([1, m]\) と区間 \([m + 1, N]\) の両方にまたがっている
2. 区間 \([1, m]\) のみに含まれる
3. 区間 \([m + 1, N]\) のみに含まれる

\(1\) を満たす任意の区間を \(2\) つの区間の和集合で表すためには

• 区間 \([i, m]\) \((1 \leq i \leq m)\)
• 区間 \([m + 1, i]\) \((m + 1 \leq i \leq N)\)

の計 \(N\) 個の区間を全て準備すればよいです。 \(2\) と \(3\) の場合は区間の長さを半減させて再帰的に考えることができます。

長さが \(1\) の区間を別途処理すると、以下のような再帰関数を書くことができます。 f(1, N)を呼び出すことで、求める \(M\) 個の整数の組が重複を除いた形で s に入ります。

set<pair<int, int>> s;

void f(int L, int R) {
  if (L == R) {
    s.insert(make_pair(L, R));
    return;
  }
  int m = (L + R) / 2;
  for (int i = L; i <= m; i++) s.insert(make_pair(i, m));
  for (int i = m + 1; i <= R; i++) s.insert(make_pair(m + 1, i));
  f(L, m);
  f(m + 1, R);
  return;
}

再帰の深さは \(\lceil \log_2 N \rceil + 1\) であり、それぞれの深さにおいて高々 \(N\) 個の区間が作成されるため、重複ありの状態で \(M \leq N (\lceil \log_2 N \rceil + 1)\) となります。 実際は長さ \(1\) の区間が多く重複しているため、 \(N \leq 4000\) であれば \(M\) は上限の \(50000\) 以下に収まります。

実装例 (C++) : https://atcoder.jp/contests/abc282/submissions/37961704

（余談ですが、このように構築すると、長さ \(2\) 以上の任意の区間を「互いに重ならない」 \(2\)つの区間の和集合で表せます。）