ABC 379 F — Buildings 2

考察

両視点から見える候補xはrより東でlから見えるものに一致する。可視性は中間ビルだけに依存し視点自身の高さは含まない。右から左へ進むと新たに中間へ入るビルが、それより低い東側候補だけを遮るので単調stackが使える。query(l,r)はlを挿入する前に答え、その後H_lより低い末尾をpopしてlを追加する。候補indexは単調なのでrを越す個数を二分探索できる。

典型の発動条件

可視要素の monotone stack

発動条件: 各位置から右を見た record high の列を多数 query したいとき。

走査方向を揃えて可視候補を stack で維持する。

問題固有の要素

二条件の一方が他方を含意することを証明すると、共通集合問題が一視点だけの query になる。

別の問題へ持ち帰る視点: query を左端でオフライン整列すると、位置ごとの可視 stack を一度ずつ構成できる。

正当性

x>rがlから見えるなら全中間高さはH_xより低い。rからxまでの中間位置はその部分集合なのでrからも見える。右からのstackは視点lの処理直前にlより東の可視候補を持つ。queryへ答えた後、H_lより低い末尾候補をpopしlをpushすると、次の視点l−1に対しlが遮る候補だけを除ける。各indexは一度だけpush/popされる。

実装上の注意

queryをstack更新前に処理する。pop条件はtopの高さ<H_l。高さは順列なので同値はない。r自身を含めずindex>rだけを数える。

復習の核

H=(3,1,2),(l,r)=(1,2)で答え1を確認し、視点高さを遮蔽物へ入れない。query→低いtop削除→l挿入の順を再現する。

計算量と制約

時間

O(N+Q log N)、stack構築は償却O(N)、各照会はindex列の二分探索。

空間

O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq H_i \leq N; H_i\neq H_j\ (i\neq j); 1 \leq l_i < r_i \leq N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Buildings 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 支配関係から不要な候補を単調stack・queueで削る

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

      主タグ: 単調stack・queueによる支配候補の削除

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

      学習の位置

      体系上の位置: 支配関係から不要な候補を単調stack・queueで削る

      • 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。

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

      • 全候補から極値を反復取得するheap・ordered set。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題