D - Divide Interval Editorial by evima

別解

トップダウンに再帰する方針を述べます。(セグメントツリーの再帰的な実装とほぼ同じです。)以下、数列 \(l, l+1, \dots, r-2, r-1\)\([l, r)\) と書きます。

良い数列 \([l, r)\) に対し、それと入力で与えられた数列 \([L, R)\) の共通部分の最適な分割を \(f(l, r, L, R)\) とします。(共通部分がない場合は考えません。)答えは \(f(0, 2^{60}, L, R)\) です。

\(f(l, r, L, R)\) を再帰的に求めましょう。

  • \([l, r)\) の全体が \([L, R)\) に含まれる場合、共通部分は \([l, r)\) で、これ自体が最適な「分割」です。
  • そうでない場合、\(m = (l + r) / 2\) とします。ここで、\([l, r)\) の左半分 \([l, m)\) と右半分 \([m, r)\) はともに良い数列です。
    • \([L, R)\) の全体が \([l, r)\) の左半分 \([l, m)\) に含まれるなら、つまり \(R \leq m\) なら、右半分は無視でき、最適な分割は \(f(l, m, L, R)\) です。
    • \([L, R)\) の全体が \([l, r)\) の右半分 \([m, r)\) に含まれるなら、つまり \(m \leq L\) なら、左半分は無視でき、最適な分割は \(f(m, r, L, R)\) です。
    • 上記のどちらでもないなら、\([L, R)\)\([l, r)\) の左半分と右半分の双方と共通部分を持ち、 最適な分割は \(f(l, m, L, R)\)\(f(m, r, L, R)\) を連結したものです。

これを再帰関数として実装して \(f(0, 2^{60}, L, R)\) を呼んだ際の再帰呼び出しの回数は、各層(公式解説の図を参照)で \(4\) 回以下、合計で \(60 \times 4\) 回以下です。

実装例(Python)

def f(l, r, L, R):
    if L <= l and r <= R:
        return [(l, r)]
    m = (l + r) // 2
    if R <= m:
        return f(l, m, L, R)
    if m <= L:
        return f(m, r, L, R)
    return f(l, m, L, R) + f(m, r, L, R)


L, R = map(int, input().split())
ans = f(0, 1 << 60, L, R)
print(len(ans))
for l, r in ans:
    print(l, r)

posted:
last update: