ABC 424 F — Adding Chords

考察

円を1とNの間で開くと、採用済みchordは交差しない区間族、すなわちlaminarな括弧構造になる。left endpointを+1、rightを-1とすればcandidate内部の既存端点がbalancedかで交差を判定できる。

採用する候補: prefix minimumとsumを持つsegment treeでcandidate区間の括弧列を判定する

棄却する候補: 新chordと全採用chordをpairwise比較する

全て採用されるとqueryごとO(Q)、合計O(Q²)になる。

segment tree leafを未使用0とし、nodeに(sum,minPrefix)を持つ。各[A_i,B_i]について内部rangeをfoldしsum=0かつminPrefix≥0ならYesとしてAへ+1、Bへ-1をpoint updateし、そうでなければNoとして何もしない。

典型の発動条件

laminar intervalと括弧列

発動条件: 交差しない区間族の開閉endpointがproper nestingを作る。

left/rightをparenthesisとしてcandidate内部のbalanceを検査する。

括弧monoid segment tree

発動条件: 動的な二点括弧挿入とsubstring validity queryが必要である。

(sum,minPrefix)をassociative mergeしてrange foldする。

問題固有の要素

全query endpointがdistinctなので、candidate端に既存括弧がなく、内部endpoint列だけを調べる条件がそのまま使える。

別の問題へ持ち帰る視点: endpoint衝突がないdynamic interval insertionは括弧列monoidへ直接写せる。

正当性

candidate[A,B]が既存intervalと交差しない iff (A,B)内のendpoint列に、外から入るunmatched closeも外へ出るunmatched openもない。これは区間sum=0かつrelative prefix minimum≥0という正しい括弧列条件である。 各端点は一度しか現れず、range foldと二点updateをO(log N)で処理できる。

実装上の注意

  • 内部を(A,B)とするか[A,B]としても端leafは挿入前0だが、index規約を統一する。不採用queryは更新しない。

復習の核

  • nested、disjoint、交互endpoint、外側candidate追加をbrute intersectionと比較する。

計算量と制約

時間

O(N+Q log N)、Nは円周頂点数。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 10^6; 1 \leq Q \leq 3\times 10^5; 1 \leq A_i < B_i \leq N; The 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are pairwise distinct.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Adding Chords の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
    • 円環順序・chord交差: 円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。

    主タグ: 区間monoid要約

    補助タグ: 円環順序・chord交差

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

    学習の位置

    体系上の位置: 区間monoid要約

    • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    先に読む単元:

    • 円環順序・chord交差 — 幾何の基本判定・配置・座標変換で得た考え方と実装を再利用し、円環順序・chord交差の発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題