ABC 457 E — Crossing Table Cloth

考察

座標数をN、布の枚数をMとする。閉区間の二枚を使って[S,T]を覆うには、左端Sと右端Tを誰かが担当する必要がある。布は二枚とも[S,T]内に収まらなければならない。

前処理では、区間頻度freq(L,R)、左端ごとの右端sorted list、右端ごとの左端sorted listを作る。さらにq[L]=min{R_i:L_i=L}(存在しなければ∞)、suf[L]=min_{x≥L}q[x]を用意する。これにより[L,R]内に布があることはsuf[L]≤Rと等価になる。

freq(S,T)>0なら一枚で既に全域を覆う。別の一枚が必要なので、freq(S,T)≥2、suf[S+1]≤T、suf[S]≤T−1のいずれかを検査する。後二条件は完全一致の布自身を確実に除外する。

完全一致がないなら、左端Sのlistで右端≤Tの最大値r、右端Tのlistで左端≥Sの最小値lを二分探索する。どちらかが存在しなければ失敗。存在すればr+1≥lが必要十分である。r=S,l=S+1のように隣接した布も、整数位置の布の覆いとして隙間がない。

典型の発動条件

interval unionの極値casework

発動条件: 少数intervalで指定区間をちょうど覆うqueryを多数処理するとき。

必要端点を固定し、支配的な最長・最短候補だけを比較する。

端点別sorted list

発動条件: 片端固定で他端の閾値以下最大・以上最小を問うとき。

bucket内二分探索で候補intervalを取得する。

問題固有の要素

二intervalのunion条件は両端を担う候補を強制し、極値候補が失敗すれば全候補が失敗するdominanceを使える。

別の問題へ持ち帰る視点: 完全一致objectの有無で解の形が変わる場合、先に分岐すると残り条件を少数の包含queryへ整理できる。

正当性

完全一致を使う場合、二枚目は同じ区間の別の布か、左端>Sか右端<Tの布であり、三条件が全候補を尽くす。sufによる存在判定は左端≥Lかつ右端≤Rをそのまま表す。完全一致がない場合は、左端Sの布と右端Tの布は異なる二枚である。前者の右端を最大、後者の左端を最小にすると、他のどの組よりも覆う隙間が小さい。整数区間なので隙間がない条件はr+1≥lであり、これが失敗すれば他の組でも覆えない。

実装上の注意

  • 同じ区間の二枚を使えるかはfreq≥2で判定する。setだけでは区別できない。
  • 閉じた整数位置なので、隙間判定はr+1≥l。suf[N+1]=∞を置き、空の内部区間を不成立として扱う。

復習の核

  • 完全一致あり/なしで全解形を列挙し、なしcaseの二つの極値候補が他候補を支配することを端点不等式で示す。

計算量と制約

時間

O(N+M log M+Q log M)。座標配列とsuffix最小にO(N)、布のbucket sortにO(M log M)、各照会に定数回の二分探索。

空間

O(N+M)。照会を逐次出力する。

制約との対応

公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 2 \times 10^5; 2 \le M \le 2 \times 10^5; 1 \le L_i \le R_i \le N; 1 \le Q \le 2 \times 10^5; 1 \le S_q \le T_q \le N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Crossing Table Cloth の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

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

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

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

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題