AtCoder Beginner Contest 282 F問題 Union of Two Sets
問題
提出解答
問題の概要
インタラクティブ問題
次の2つの Phase を完遂せよ.
Phase 1
が与えられる.
以上
以下の整数
を出力する.
個の整数の組
を出力する. ただし,
でなくてはならない.
Phase 2
が与えられる.
- 以下を
回行う.
回目は以下である.
が与えられる.
- 以下を満たす
以上
以下の整数
を出力する:
制約
は Phase 1 の出力から決定される.
解法
の部分集合族
を
とする. このとき, であるから,
の条件を満たす.
の元は,
の部分集合で, 長さが
ベキであるような区間である.
に関するクエリを考える.
となる最大の整数
を取ってきた時,
である.
なお, この問題は Sparse Table というデータ構造を背景とした問題である.