ABC 282 F — Union of Two Sets

考察

任意query区間を事前登録2区間のunionで表すには、重なりを許せることが重要で、disjoint分解を2個に限定する必要はない。

長さlenに対し最大の2^k≤lenを選ぶと、左端からの長さ2^k区間と右端までの長さ2^k区間が重なりつつ全[L,R]を覆う。

採用する候補: 長さ1,2,4,…の全開始位置区間を登録し、queryを同じ長さの左prefix区間と右suffix区間の2個で答える。

棄却する候補: 全N(N+1)/2区間を登録してquery自身を1個選ぶ。

N=4000でM上限50000を大きく超える。

k=0…floor(log2N)、l=1…N-2^k+1の区間[l,l+2^k-1]を列挙しid[k][l]を保存して出力する。query[L,R]ではk=floor(log2(R-L+1))としてid[k][L]とid[k][R-2^k+1]を返す。

典型の発動条件

sparse tableのoverlapping decomposition

発動条件: idempotent queryやunion表現で、区間を同長power-of-two区間2個へ分けられるとき。

最大2冪長の左・右blockを重ねて全区間を覆う。

offline family design

発動条件: query前に制限個数の集合族を提示し、後から任意区間を少数集合で表すとき。

全power-of-two intervalをuniversal familyとして登録する。

問題固有の要素

unionでは重複が無視されるため、sparse tableと同じoverlap分解がそのままinteractive構成になる。

別の問題へ持ち帰る視点: 二つの集合で区間を表す問題では、重なり許容なら最大2冪の両端coverを試す。

正当性

2^k≤len<2^{k+1}なので、左右2区間の合計長2^{k+1}はlen以上となりgapがなく、どちらも[L,R]内なのでunionが正確にquery区間になる。 各(power,start)に出力indexを記録すれば、phase2は二つのtable lookupだけでよい。 登録数N(logN+1)が50000以内で、各queryをlog tableから定数時間で復元できる。

実装上の注意

  • N=4000で登録数が48000以下になることを出力前に確認し、idは1-indexedの出力順と一致させる。
  • 各phase出力後にflushし、lenが2冪なら左右idが同一でもa=bが許される。

復習の核

  • len=5,6,7とlen=8で左右の長さ4/8区間を描き、gapがなく外へはみ出さないことを確認する。

計算量と制約

時間

登録O(N log N)、各質問O(1)。

空間

O(N log N)、登録ID表。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 4000; 1 \leq Q \leq 10^5; 1 \leq L \leq R \leq N; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Union of Two Sets の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 冪等演算のoverlap range query・Sparse Table

主題
  • 冪等演算のoverlap range query・Sparse Table: 冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 対話protocolを守って情報を取得する: judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。

    主タグ: 冪等演算のoverlap range query・Sparse Table

    補助タグ: 対話protocolとquery設計

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 冪等演算のoverlap range query・Sparse Table

    • 冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 対話protocolを守って情報を取得する — 問い合わせ形式・回数上限・応答依存性・交互手番・合法な応答・flushを明示し、アルゴリズムをjudgeとの対話列として安全に実行する。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題