ABC 389 F — Rated Range

考察

初期rating xからi contest後の値D_i(x)はxについて単調非減少で、一度二つの軌道が同値になれば以後も同じ更新を受ける。

contest [L,R]で+1される初期値xの集合は、単調なD(x)のpreimageなので一つの連続区間になる。

採用する候補: 全初期ratingの現在値をrange-add segment treeで持ち、各contestのpreimage区間をtree上探索して+1する

棄却する候補: queryごとにN contestを逐次simulationする

O(NQ)でN=2×10^5,Q=3×10^5に間に合わない。

D[x]=xで初期化する。各[L_i,R_i]についてD値がL_i以上になる最初lとR_iより大きくなる最初rをsegment treeのsearchで求め、初期index区間[l,r)へ+1する。最後にquery Xの点値を返す。

典型の発動条件

monotone functionのpreimage更新

発動条件: 多数の初期状態へ同じ単調transitionを適用し、条件成立域が値区間で与えられるとき。

現在値配列のlower/upper boundを求め初期状態区間へ作用する。

発動条件: 単調配列を区間加算しながら値境界を検索するとき。

lazy treeのmax_right/min_leftでpreimage端を求める。

問題固有の要素

時間軸をqueryごとに辿る代わりに、全初期値を横に並べた写像Dを一括更新すると、rating条件が区間作用になる。

別の問題へ持ち帰る視点: 独立simulationが多数あるとき、初期条件→現在状態の単調写像をまとめて持てないか検討する。

正当性

D配列は単調だがstrict増加とは限らないため、lower_bound(L)とupper_bound(R)でpreimage境界を取る。 rating上限は初期最大にcontest増分を見込んだ範囲までsegment treeへ確保するか、query対象domainだけを管理する。 各contestでD(x)∈[L,R]となる最初・最後のxをmonoid searchでO(log X)に求め、区間加算できるため全体O((N+Q)log X)となる。

実装上の注意

  • 同じD値が連続するので二分探索条件の≤/<を区別する。segment treeの管理domainが全query Xを含むことを確認する。

復習の核

  • 初期値軌道が合流するcase、L=R、更新区間が空/全域になる小domainを全simulationと比較し、upper bound境界を確認する。

計算量と制約

時間

O(X+N log X+Q log X)、Xは管理する初期rating数、Nはcontest数。

空間

O(X)。

制約との対応

公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N); 1 \leq Q \leq 3 \times 10^5; For each query, 1 \leq X \leq 5 \times 10^5.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Rated Range の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間更新を要約へ作用させる

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 遅延評価する区間作用

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

      学習の位置

      体系上の位置: 区間更新を要約へ作用させる

      • 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

      先に読む単元:

      • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      この解説で扱わないこと:

      • 過去の版の保存・rollback・構造共有。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題